{"problem":{"name":"「TAOI-1」椎名真昼","description":{"content":"你正在看轻小说，突然你的家长走了进来，于是你假装在写 OI 题目。 Alice 和 Bob 正在玩一款游戏，给定一个有向图，每个点初始有一个颜色（黑或白）。 双方轮流进行操作，Alice 先手，每次操作选定一个节点，将所有从该点开始，能到达的点（包括自身）颜色翻转。如果某次操作后所有节点都变为白色，则进行该次操作的人胜利。 假如双方都采用最优策略使得自己胜利，或者如果自己无法胜利，使得对方无","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9220"},"statements":[{"statement_type":"Markdown","content":"你正在看轻小说，突然你的家长走了进来，于是你假装在写 OI 题目。\n\nAlice 和 Bob 正在玩一款游戏，给定一个有向图，每个点初始有一个颜色（黑或白）。\n\n双方轮流进行操作，Alice 先手，每次操作选定一个节点，将所有从该点开始，能到达的点（包括自身）颜色翻转。如果某次操作后所有节点都变为白色，则进行该次操作的人胜利。\n\n假如双方都采用最优策略使得自己胜利，或者如果自己无法胜利，使得对方无法胜利。\n\n给你节点的初始状态，请你求出最终的胜者，亦或者，没有胜者。\n\n---\n\n定义点 $u$ 能到达点 $v$，当且仅当存在数列 $(a_1,a_2,a_3,\\cdots,a_k)$，其中 $k \\ge 1$，使得 $\\forall i \\in [1,k)$，存在有向边 $a_i \\to a_{i+1}$，且 $a_1=u$，$a_k=v$。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行一个正整数 $T$，代表数据组数。\n\n对于每组测试数据：\n\n第一行两个整数 $n, m$，代表图的点数，边数。\n\n第二行 $n$ 个整数，代表每个点开始时的颜色。$1$ 代表黑色，$0$ 代表白色。\n\n接下来 $m$ 行，每行两个整数 $u, v$ 代表一条从 $u \\to v$ 的边。\n\n## Output\n\n对于每组测试数据：\n\n如果最后 Alice 胜利，输出 `A`。\n\n如果最后 Bob 胜利，输出 `B`。\n\n如果双方（在对方的阻止下）都无法胜利，输出 `N`。\n\n您无需输出空格或换行符。\n\n[samples]\n\n## Background\n\n**请注意赛后题目添加了多测。因此请将您的赛时代码进行修改后再提交。**\n\n## Note\n\n### 数据范围\n\n**本题采用捆绑测试**。\n\n- Subtask 1（5 points）：$n \\leq 2$，$m \\leq 1$，$T=1$。\n- Subtask 2（15 points）：$n \\leq 5$，$m \\leq 8$，$T=1$。\n- Subtask 3（25 points）：保证所有点的初始颜色相同。\n- Subtask 4（55 points）：无特殊限制。\n\n对于所有测试数据，$1 \\leq n \\leq 10^5$，$1 \\leq m \\leq 2 \\times 10^5$，$1 \\le T \\le 15$。\n\n### 样例解释\n\n在第一组数据中，Alice 可以先手对节点 $1$ 进行操作。操作后所有节点变为白色。\n\n在第二组数据中，双方都没有必胜的方法，因此双方会互相拖延对方阻止对方获胜。\n\n---\n\n「据说如果无论如何都输出 `N` 的话，有 $45\\%$ 的几率能够得到正确答案？」\n\n「怎么可能，不会真的有人造出这么蠢的数据吧……」","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9220","tags":["博弈论","O2优化","拓扑排序","强连通分量","Tarjan"],"sample_group":[["2\n2 1\n1 0\n2 1\n3 2\n1 0 1\n1 2\n2 3","AN"]],"created_at":"2026-03-03 11:09:25"}}