← 返回题目列表

Codeforces · 1991/E

E. 着色游戏

中文机器翻译题面 查看原题

这是一个交互问题。

考虑一个由 $$$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 获胜,因为不存在具有相同颜色顶点的边。