这是一个交互问题。
考虑一个由 $$$n$$$ 个顶点和 $$$m$$$ 边组成的无向连通图。每个顶点都可以使用以下三种颜色之一进行着色:$$$1$$$、$$$2$$$ 或 $$$3$$$。最初,所有顶点都是未着色的。
Alice 和 Bob 正在玩一个由 $$$n$$$ 轮组成的游戏。在每一轮中,都会发生以下两步过程:
1. Alice 选择两种不同的颜色。
2. Bob 选择一个未着色的顶点,并使用 Alice 选择的两种颜色之一为其着色。
如果存在连接相同颜色的两个顶点的边,则 Alice 获胜。否则,鲍勃获胜。
您将获得图表。你的任务是决定你想扮演哪位玩家并赢得比赛。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \le n \le 10^4$$$, $$$n - 1 \le m \le \min(\frac{n \cdot (n - 1)}{2}, 10^4)$$$) — 图中的顶点数和边数,分别。
每个测试用例接下来的 $$$m$$$ 行都包含两个整数 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) - 图的边。保证图是连通的,并且不存在重边或自环。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$10^4$$$。
互动
对于每个测试用例,您需要输出一行包含“Alice”或“Bob”,代表您选择的玩家。
然后,对于以下 $$$n$$$ 轮中的每一轮,都会发生以下两步过程:
1. Alice(您或交互者)将输出两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le 3$$$, $$$a \neq b$$$) — Alice 选择的颜色。
2. Bob(您或交互者)将输出两个整数 $$$i$$$ 和 $$$c$$$ ($$$1 \le i \le n$$$, $$$c = a$$$ 或 $$$c = b$$$) — Bob 选择的顶点和颜色。顶点 $$$i$$$ 必须是先前未着色的顶点。
如果您的任何输出无效,陪审团将输出“-1”,您将收到错误答案判决。
在所有 $$$n$$$ 回合结束时,如果您输掉了比赛,陪审团将输出“-1”,您将收到错误答案的判决。
如果您的程序收到 $$$-1$$$ 而不是有效值,则它必须立即终止。否则,您可能会收到任意判决,因为您的解决方案可能正在从封闭的流中读取。
请注意,如果您扮演 Alice,并且已经存在连接两个相同颜色顶点的边,则交互器不会提前终止,您将继续玩所有 $$$n$$$ 轮。
输出后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
在这个问题中,黑客被禁用。
示例
输入 #1
2 3 3 1 2 2 3 3 1 3 1 2 2 1 1 4 4 1 2 2 3 3 4 4 1 2 3 1 2 2 1 3 1
输出 #1
Alice 3 1 1 2 2 1 Bob 1 2 2 1 4 1 3 3
注意
请注意,示例测试用例是示例游戏,并不一定代表双方玩家的最佳策略。
在第一个测试用例中,您选择扮演 Alice。
1. Alice 选择两种颜色:$$$3$$$ 和 $$$1$$$。 Bob 选择顶点 $$$3$$$ 并用颜色 $$$1$$$ 为其着色。
2. Alice 选择两种颜色:$$$1$$$ 和 $$$2$$$。 Bob 选择顶点 $$$2$$$ 并用颜色 $$$2$$$ 为其着色。
3. Alice 选择两种颜色:$$$2$$$ 和 $$$1$$$。 Bob 选择顶点 $$$1$$$ 并用颜色 $$$1$$$ 为其着色。
Alice 获胜,因为边 $$$(3, 1)$$$ 连接两个相同颜色的顶点。
在第二个测试用例中,您选择扮演 Bob。
1. Alice 选择两种颜色:$$$2$$$ 和 $$$3$$$。 Bob 选择顶点 $$$1$$$ 并用颜色 $$$2$$$ 为其着色。
2. Alice 选择两种颜色:$$$1$$$ 和 $$$2$$$。 Bob 选择顶点 $$$2$$$ 并用颜色 $$$1$$$ 为其着色。
3. Alice 选择两种颜色:$$$2$$$ 和 $$$1$$$。 Bob 选择顶点 $$$4$$$ 并用颜色 $$$1$$$ 为其着色。
4. Alice 选择两种颜色:$$$3$$$ 和 $$$1$$$。 Bob 选择顶点 $$$3$$$ 并用颜色 $$$3$$$ 为其着色。
Bob 获胜,因为不存在具有相同颜色顶点的边。