Background

Please note that multiple test cases were added after the contest. Therefore, please modify your contest code before submitting.

Problem Description

You are reading a light novel, and suddenly your parents walk in, so you pretend that you are solving OI problems.

Alice and Bob are playing a game. Given a directed graph, each node initially has a color (black or white).

They take turns making moves, with Alice going first. In each move, they choose a node and flip the colors of all nodes that are reachable from that node (including the node itself). If after some move all nodes become white, then the player who made that move wins.

Assume both players use optimal strategies: they try to make themselves win, or if they cannot win, they try to prevent the other player from winning.

Given the initial state of the nodes, determine the final winner, or determine that there is no winner.

Define that node $u$ can reach node $v$ if and only if there exists a sequence $(a_1,a_2,a_3,\cdots,a_k)$, where $k \ge 1$, such that for all $i \in [1,k)$ there is a directed edge $a_i \to a_{i+1}$, and $a_1=u$, $a_k=v$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

The first line contains two integers $n, m$, representing the number of nodes and the number of edges in the graph.

The second line contains $n$ integers, representing the initial color of each node. $1$ means black, and $0$ means white.

The next $m$ lines each contain two integers $u, v$, representing an edge from $u \to v$.

Output Format

For each test case:

If Alice wins in the end, output A.

If Bob wins in the end, output B.

If neither side can win (due to the other side's obstruction), output N.

You do not need to output spaces or newline characters.

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

AN

Hint

Constraints

This problem uses bundled tests.

• 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): It is guaranteed that all nodes have the same initial color.
• Subtask 4 (55 points): No special restrictions.

For all testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$, $1 \le T \le 15$.

Sample Explanation

In the first test case, Alice can make the first move on node $1$. After the move, all nodes become white.

In the second test case, neither side has a forced-win strategy, so they will keep stalling each other and prevent the other from winning.

"It is said that if you output N no matter what, there is a $45\%$ chance to get the correct answer?"

"No way. Could it be that someone actually made such stupid testdata..."

Translated by ChatGPT 5