CF1991E.Coloring Game

这是一个交互题。

给定一个包含 $n$ 个顶点和 $m$ 条边的无向连通图。每个顶点可以被染成三种颜色之一：$1$、$2$ 或 $3$。初始时，所有顶点都是未染色的。

Alice 和 Bob 进行一个包含 $n$ 轮的游戏。在每一轮中，进行如下两步：

1. Alice 选择两种不同的颜色。
2. Bob 从未染色的顶点中选择一个，并用 Alice 选的两种颜色之一为其染色。

如果存在一条边连接了两个颜色相同的顶点，则 Alice 获胜。否则，Bob 获胜。

你将得到这张图。你的任务是决定你想扮演哪一位玩家，并赢得这场游戏。

每个测试包含多组测试用例。第一行包含一个整数 $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"，你将收到 Wrong Answer 判定。

在所有 $n$ 轮结束后，如果你输了游戏，评测机会输出 "-1"，你将收到 Wrong Answer 判定。

如果你的程序收到了 $-1$ 而不是有效值，必须立即终止。否则，你可能会因为读取已关闭的流而收到任意判定。

注意，如果你扮演 Alice，并且已经存在一条边连接了两个颜色相同的顶点，交互器不会提前终止，你仍需完成所有 $n$ 轮。

输出后不要忘记换行并刷新输出流，否则会因超时被判为 Idleness limit exceeded。具体做法如下：

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

本题不支持 Hack。

注意，样例测试用例仅为示例游戏，不一定代表双方的最优策略。

在第一个测试用例中，你选择扮演 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 获胜，因为没有任何一条边连接了两个颜色相同的顶点。

由 ChatGPT 4.1 翻译