这是一道交互题。

小青鱼有一张包含 $n$ 个顶点和 $m$ 条边的简单无向图，顶点标号为 $1$ 到 $n$，边标号为 $1$ 到 $m$。最初，顶点 $i$ 的颜色为 $i$。

两位玩家 A 和 B 玩一个包含 $m$ 轮的游戏。在每一轮中，两位玩家按顺序执行以下操作：

• 玩家 A 选择一条在之前的任何一轮中都未被选择过的边 $(u, v)$。
• 玩家 B 选择这条边的一个端点，并将其颜色修改为另一个端点当前的颜色。

在全部 $m$ 轮结束后，如果所有顶点的颜色都相同，则玩家 B 获胜。否则，玩家 A 获胜。

小青鱼希望你判断哪位玩家可以无论对手如何操作都保证获胜。然后作为该玩家与他对局并赢得游戏。

输入格式

本题有多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5$，$1 \le m \le 10^5$），分别表示顶点的数量和边的数量。

接下来 $m$ 行描述各条边。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示边 $i$ 连接顶点 $u_i$ 和 $v_i$。

保证图中没有自环或重边。图可能是不连通的。

保证所有测试数据中 $n$ 的总和不超过 $10^5$，且所有测试数据中 $m$ 的总和不超过 $10^5$。

在读入一张图后，请先完成该组测试数据的交互，再读入下一张图。

交互

为了选择你的角色，请输出一行，包含 A 或 B。如果玩家 A 可以保证获胜则输出 A，如果玩家 B 可以保证获胜则输出 B。小青鱼将扮演另一位玩家。

然后按如下方式进行恰好 $m$ 轮游戏。

• 如果你扮演 A，输出一行一个整数 $e$（$1 \le e \le m$），表示一条在之前的任何一轮中都未被选择过的边的编号。作为回应，你将在一行中读入一个整数 $x$。顶点 $x$ 是边 $e$ 的一个端点，且它的颜色被修改为另一个端点当前的颜色。
• 如果你扮演 B，在一行中读入一个整数 $e$（$1 \le e \le m$），表示一条在之前的任何一轮中都未被选择过的边的编号。输出一行一个整数 $x$，表示边 $e$ 的一个端点。顶点 $x$ 的颜色将被修改为另一个端点当前的颜色。

在全部 $m$ 轮结束后，读入一个整数。如果你选择了正确的角色并赢得了游戏，该整数为 1。收到 1 后，请继续处理下一组测试数据。在最后一组测试数据结束后，你的程序应当终止。

如果你选择了错误的角色、进行了不合法的操作，或者输掉了游戏，交互器将发送 -1。如果你在任意时刻收到 -1，你的程序应当立即终止。

在输出你的角色或操作后，请不要忘记输出换行符并刷新输出缓冲区。

测试工具： 题目提供了一个测试工具，以帮助选手开发和测试自己的程序。你可以从附件中下载该工具。使用 -h 选项运行该工具可以显示使用说明。该测试工具仅涵盖官方交互器支持的部分测试场景与功能。

样例

输入格式 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

输出格式 1

B

3

1






A
1

3

2

说明

样例中的两局游戏如下所示。在每一步中，A 选择高亮显示的边，B 将画圈的顶点重新染色。虚线边表示在之前已经被选择过的边。