CF1147F.Zigzag Game

You are given a complete bipartite graph with $2n$ nodes, with $n$ nodes on each side of the bipartition. Nodes $1$ through $n$ are on one side of the bipartition, and nodes $n+1$ to $2n$ are on the other side. You are also given an $n \times n$ matrix $a$ describing the edge weights. $a_{ij}$ denotes the weight of the edge between nodes $i$ and $j+n$. Each edge has a distinct weight.

Alice and Bob are playing a game on this graph. First Alice chooses to play as either "increasing" or "decreasing" for herself, and Bob gets the other choice. Then she places a token on any node of the graph. Bob then moves the token along any edge incident to that node. They now take turns playing the following game, with Alice going first.

The current player must move the token from the current vertex to some adjacent unvisited vertex. Let $w$ be the last weight of the last edge that was traversed. The edge that is traversed must be strictly greater than $w$ if the player is playing as "increasing", otherwise, it must be strictly less. The first player unable to make a move loses.

You are given $n$ and the edge weights of the graph. You can choose to play as either Alice or Bob, and you will play against the judge. You must win all the games for your answer to be judged correct.

Interaction

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). Description of the test cases follows.

Each test starts with an integer $n$ ($1 \leq n \leq 50$) — the number of nodes on each side of the bipartition.

The next $n$ lines contain $n$ integers $a_{ij}$ ($1 \leq a_{ij} \leq n^2$). $a_{ij}$ denotes the weight of the edge between node $i$ and node $j+n$. All $a_{ij}$ will be distinct.

You first print a string "A" or "B", denoting which player you want to play ("A" for Alice and "B" for Bob).

If playing as Alice, first print either "I" or "D" (denoting whether you choose "increasing" or "decreasing"). Then, print the node that you wish to start at.

If playing as Bob, read in a character "I" or "D" (denoting whether the judge chose "increasing" or "decreasing"), then the node that the judge chooses to start at.

To make a move, print the index of the node that you wish to go to. To read what move the judge made, read an integer from standard in.

If the judge responds with $-1$, then that means the judge has determined it has no legal moves (or it may have just given up) and that you won the case. Stop processing this case immediately and start processing the next case.

If the judge responds with $-2$, that means that the judge has determined that you made an invalid move, so you should exit immediately to avoid getting other verdicts.

If you are unable to make a move or give up, print $-1$ and then exit immediately. This will give you a Wrong answer verdict.

After printing a move do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer $t$ ($t=1$).

The second line should contain an integer $n$ ($1 \leq n \leq 50$).

The next $n$ lines should contain $n$ integers each, the $a_{ij}$ ($1 \leq a_{ij} \leq n^2$). $a_{ij}$ denotes the weight of the edge between node $i$ and node $j+n$. All $a_{ij}$ must be distinct.

The judge will play a uniformly random legal move with this case versus the hacked program. If it has no legal moves left, it will give up and declare the player as the winner.

你被给定一个包含 $2n$ 个节点的完全二分图，二分图的每一侧各有 $n$ 个节点。编号为 $1$ 到 $n$ 的节点位于二分图的一侧，编号为 $n+1$ 到 $2n$ 的节点位于另一侧。你还被给定一个 $n \times n$ 的矩阵 $a$，用于描述边的权重：$a_{ij}$ 表示节点 $i$ 与节点 $j+n$ 之间的边的权重。每条边的权重互不相同。

爱丽丝（Alice）和鲍勃（Bob）正在该图上进行一场游戏。首先，爱丽丝选择自己扮演“递增”（increasing）或“递减”（decreasing）角色，鲍勃则自动获得另一角色。接着，爱丽丝将一个标记（token）放置在图中任意一个节点上；随后鲍勃必须沿一条与该节点关联的边移动该标记。此后双方轮流进行如下操作，且爱丽丝先手：

当前玩家必须将标记从当前顶点沿一条边移动至某个未访问过的相邻顶点。设 $w$ 为上一次所经过边的权重，则本次所选边的权重必须满足：若该玩家扮演“递增”，则其权重必须严格大于 $w$；否则（即扮演“递减”），其权重必须严格小于 $w$。首位无法进行合法移动的玩家判负。

你被给定 $n$ 及图中所有边的权重。你可以选择作为爱丽丝或鲍勃进行游戏，并将与评测程序（judge）对战。为使你的解答被判为正确，你必须赢得所有测试用例。

交互方式

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 50$）。随后是各测试用例的描述。

每个测试用例以一个整数 $n$（$1 \leq n \leq 50$）开始，表示二分图每侧的节点数。

接下来 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$（$1 \leq a_{ij} \leq n^2$），其中 $a_{ij}$ 表示节点 $i$ 与节点 $j+n$ 之间边的权重。所有 $a_{ij}$ 均互不相同。

你首先输出一个字符串 "A" 或 "B"，表示你希望扮演的角色（"A" 表示爱丽丝，"B" 表示鲍勃）。

• 若你选择扮演爱丽丝，则需先输出字符 "I" 或 "D"（分别表示你选择“递增”或“递减”），然后输出你希望起始放置标记的节点编号。
• 若你选择扮演鲍勃，则需先读入一个字符 "I" 或 "D"（表示评测程序为你选择的角色），再读入评测程序选定的起始节点编号。

每次进行移动时，输出你希望移动至的目标节点编号（即节点索引）。每次对手（评测程序）移动后，你需要从标准输入读取一个整数，以获知其移动的目标节点。

• 若评测程序返回 $-1$，表示其判定已无合法移动可走（或主动认输），你赢得本测试用例。请立即停止处理当前用例，并开始处理下一个用例。
• 若评测程序返回 $-2$，表示其判定你执行了非法移动，此时你应立即退出程序，以免收到其他错误提示。
• 若你无法进行合法移动或主动认输，请输出 $-1$ 并立即退出。这将导致“答案错误”（Wrong answer）判决。

每次输出移动操作后，务必输出换行符并刷新输出缓冲区。否则你会收到“空闲超时”（Idleness limit exceeded）提示。刷新方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

Hack 格式（用于构造测试数据）

要 hack（提供自定义测试数据），请使用以下格式。注意：你仅能提交一个测试用例。

第一行应为单个整数 $t$（$t = 1$）。

第二行为一个整数 $n$（$1 \leq n \leq 50$）。

接下来 $n$ 行，每行含 $n$ 个整数，即 $a_{ij}$（$1 \leq a_{ij} \leq n^2$），其中 $a_{ij}$ 表示节点 $i$ 与节点 $j+n$ 之间边的权重。所有 $a_{ij}$ 必须互不相同。

评测程序将针对该测试用例，以均匀随机的方式选择一个合法移动，与被 hack 的程序对战。若评测程序已无合法移动，则会主动认输，并宣布当前轮到行动的玩家获胜。

The first example has two test cases. In the first test case, the graph looks like the following.

In the sample output, the player decides to play as Alice and chooses "decreasing" and starting at node $3$. The judge responds by moving to node $6$. After, the player moves to node $2$. At this point, the judge has no more moves (since the weight must "increase"), so it gives up and prints $-1$.

In the next case, we have two nodes connected by an edge of weight $1$. The player decides to play as Bob. No matter what the judge chooses, the player can move the token to the other node and the judge has no moves so will lose.

第一个样例包含两个测试用例。在第一个测试用例中，图的结构如下所示：

在样例输出中，玩家选择扮演 Alice，并选定策略为“递减”，且从节点 $3$ 开始。裁判响应，将标记移动到节点 $6$；随后玩家将标记移动到节点 $2$。此时裁判已无合法移动（因为边权必须“递增”），于是认输并输出 $-1$。

在下一个测试用例中，图中仅有两个节点，由一条权重为 $1$ 的边相连。玩家选择扮演 Bob。无论裁判如何选择，玩家均可将标记移至另一节点，此时裁判已无合法移动，因而失败。