CF1991E翻译

· · 闲话

题目传送门

题目描述

这是一个交互题。

给定一个有 n 个点和 m 条边的无向图，每个点都可以被 1、2、3 三种颜色涂色，一开始所有点都没有被涂色。

Alice和Bob正在进行 n 轮这样的游戏。在每轮游戏中，接下来两个过程依次发生：

  1. Alice选择两种不同的颜色；

  2. Bob选择一个没有被染色过的点，并用Alice选择的两个颜色之一对这个点染色。

如果存在一条边连接着两个相同颜色的点，那么Alice赢，反之Bob赢。

现在给出这张图，你的任务就是选择一个角色并赢下这场游戏。

输入格式

每个测试点包含多组测试样例。

第一行输入一个整数 t(1 \le t \le 10^3)，代表有 t 组测试样例，对每组样例：

第一行输入两个整数 n(1 \le n \le 10^4),m(n-1 \le m \le min [ \frac{n(n-1)}{2},10^4 ] )代表有 n 个点和 m 条边。

接下来 m 行输入两个整数 u,v(1 \le u,v \le n)，代表 u,v 之间有一条双向边。数据保证是连通图且无多余的边或单独的环。

数据保证 \sum_{i=1}^{t}n_i \le 10^4, \sum_{i=1}^{t}m_i \le 10^4

输出格式

对于每组样例：

第一行输出"Alice"或"Bob"，代表您选择的角色

接下来n轮游戏，两个过程会依次进行：

  1. Alice输出两个整数 a,b(1 \le a,b \le 3且a \ne b) ，代表Alice选择的两种颜色
  2. Bob输出两个整数 i,c(1 \le i\le n,c=a或c=b) ，代表Bob选择第 i 个节点染上第 c 种颜色

您只需输出您选择的角色的游戏过程，另一角色由评测机输出。

若你输出了不合法数据或者输了这场游戏，那么评测机会输出 -1，并且你会得到 Wrong Answer 的结果，此时您必须立即终止程序。

需要注意的是，如果您选择了Alice且已经存在一条边连着两个相同颜色的点，评测机不会提前结束，您也需要继续输出直到 n 轮结束。

在输出后，别忘了用以下语句清空缓冲区：

C++语言:fflush(stdout) 或 cout.flush()
Java语言：System.out.flush()
Pascal语言：flush(output)
Python语言：stdout.flush()
其他语言：请参阅相关文档

样例输出

样例输入

详见原题描述

样例解释

需要指出，样例中双方的交互并不一定代表最佳策略

在第一个样例中，您选择了Alice这个角色：

  1. Alice选择3、1两种颜色；Bob选择将第3个节点染成颜色1
  2. Alice选择1、2两种颜色；Bob选择将第2个节点染成颜色2
  3. Alice选择2、1两种颜色；Bob选择将第1个节点染成颜色1

最后，连接1、3号节点的边满足题意，所以Alice获胜

在第二个样例中，您选择了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获胜