染色游戏

时间限制：2 秒
空间限制：256 MB

这是一道交互题。

考虑一个由 $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\left(\frac{n(n-1)}{2}, 10^4\right)$），分别表示顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示图中的一条边。保证图是连通的，且没有重边或自环。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $10^4$。

交互方式

对于每组测试数据，你需要先输出一行，内容为 Alice 或 Bob，表示你选择扮演的角色。

随后的 $n$ 轮中，每轮按以下两步进行：

• 若你扮演 Alice，则你需要输出两个不同的整数 $a$ 和 $b$（$1 \le a, b \le 3$，$a \ne b$），表示你选择的两种颜色。
• 若你扮演 Bob，则对方（交互器）会输出两个整数 $a$ 和 $b$，你需要接着输出两个整数 $i$ 和 $c$（$1 \le i \le n$，且 $c = a$ 或 $c = b$），表示你选择一个未染色的顶点 $i$ 并染成颜色 $c$。

如果你扮演 Alice，交互器会在你的每次输出后给出 Bob 的选择；如果你扮演 Bob，交互器会先给出 Alice 的选择，你需要及时响应。

如果你的输出不合法，交互器会输出 -1 并终止。此时你必须立即结束程序，否则可能得到任意评测结果。若游戏结束时你失败了，交互器同样会输出 -1。

注意：如果你扮演 Alice 且已出现同色边，交互器不会提前终止，游戏仍会进行完 $n$ 轮。

每次输出后请换行并刷新缓冲区，例如在 C++ 中使用 cout.flush(); 或 cout << endl;。

本题禁止使用 hack。

样例输入

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

样例输出

Alice
3 1

1 2

2 1

Bob

1 2

2 1

4 1

3 3

备注

样例仅展示了一种可能的对局过程，并不代表双方的最优策略。

在第一个样例中，你选择扮演 Alice 并获胜。在第二个样例中，你选择扮演 Bob 并获胜。