「TAOI-1」椎名真昼

你正在看轻小说，突然你的家长走了进来，于是你假装在写 OI 题目。 Alice 和 Bob 正在玩一款游戏，给定一个有向图，每个点初始有一个颜色（黑或白）。 双方轮流进行操作，Alice 先手，每次操作选定一个节点，将所有从该点开始，能到达的点（包括自身）颜色翻转。如果某次操作后所有节点都变为白色，则进行该次操作的人胜利。 假如双方都采用最优策略使得自己胜利，或者如果自己无法胜利，使得对方无法胜利。 给你节点的初始状态，请你求出最终的胜者，亦或者，没有胜者。 --- 定义点 $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$。 ## Input **本题有多组测试数据。** 第一行一个正整数 $T$，代表数据组数。 对于每组测试数据： 第一行两个整数 $n, m$，代表图的点数，边数。 第二行 $n$ 个整数，代表每个点开始时的颜色。$1$ 代表黑色，$0$ 代表白色。 接下来 $m$ 行，每行两个整数 $u, v$ 代表一条从 $u \to v$ 的边。 ## Output 对于每组测试数据： 如果最后 Alice 胜利，输出 `A`。 如果最后 Bob 胜利，输出 `B`。 如果双方（在对方的阻止下）都无法胜利，输出 `N`。 您无需输出空格或换行符。 [samples] ## Background **请注意赛后题目添加了多测。因此请将您的赛时代码进行修改后再提交。** ## Note ### 数据范围 **本题采用捆绑测试**。 - Subtask 1（5 points）：$n \leq 2$，$m \leq 1$，$T=1$。 - Subtask 2（15 points）：$n \leq 5$，$m \leq 8$，$T=1$。 - Subtask 3（25 points）：保证所有点的初始颜色相同。 - Subtask 4（55 points）：无特殊限制。 对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \le T \le 15$。 ### 样例解释 在第一组数据中，Alice 可以先手对节点 $1$ 进行操作。操作后所有节点变为白色。 在第二组数据中，双方都没有必胜的方法，因此双方会互相拖延对方阻止对方获胜。 --- 「据说如果无论如何都输出 `N` 的话，有 $45\%$ 的几率能够得到正确答案？」 「怎么可能，不会真的有人造出这么蠢的数据吧……」