题目背景

请注意赛后题目添加了多测。因此请将您的赛时代码进行修改后再提交。

题目描述

你正在看轻小说，突然你的家长走了进来，于是你假装在写 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$。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，代表数据组数。

对于每组测试数据：

第一行两个整数 $n, m$，代表图的点数，边数。

第二行 $n$ 个整数，代表每个点开始时的颜色。$1$ 代表黑色，$0$ 代表白色。

接下来 $m$ 行，每行两个整数 $u, v$ 代表一条从 $u \to v$ 的边。

输出格式

对于每组测试数据：

如果最后 Alice 胜利，输出 A。

如果最后 Bob 胜利，输出 B。

如果双方（在对方的阻止下）都无法胜利，输出 N。

您无需输出空格或换行符。

2
2 1
1 0
2 1
3 2
1 0 1
1 2
2 3

AN

提示

数据范围

本题采用捆绑测试。

• 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\%$ 的几率能够得到正确答案？」

「怎么可能，不会真的有人造出这么蠢的数据吧……」