#P1991E. Coloring Game

    ID: 10738 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>constructive algorithmsdfs and similargamesgraphsgreedyinteractive

Coloring Game

Description

This is an interactive problem.

Consider an undirected connected graph consisting of nn vertices and mm edges. Each vertex can be colored with one of three colors: 11, 22, or 33. Initially, all vertices are uncolored.

Alice and Bob are playing a game consisting of nn rounds. In each round, the following two-step process happens:

  1. Alice chooses two different colors.
  2. Bob chooses an uncolored vertex and colors it with one of the two colors chosen by Alice.

Alice wins if there exists an edge connecting two vertices of the same color. Otherwise, Bob wins.

You are given the graph. Your task is to decide which player you wish to play as and win the game.

Each test contains multiple test cases. The first line contains a single integer tt (1≤t≤10001 \le t \le 1000) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers nn, mm (1≤n≤1041 \le n \le 10^4, n−1≤m≤min⁡(n⋅(n−1)2,104)n - 1 \le m \le \min(\frac{n \cdot (n - 1)}{2}, 10^4)) — the number of vertices and the number of edges in the graph, respectively.

Each of the next mm lines of each test case contains two integers uiu_i, viv_i (1≤ui,vi≤n1 \le u_i, v_i \le n) — the edges of the graph. It is guaranteed that the graph is connected and there are no multiple edges or self-loops.

It is guaranteed that the sum of nn and the sum of mm over all test cases does not exceed 10410^4.

Interaction

For each test case, you need to output a single line containing either "Alice" or "Bob", representing the player you choose.

Then for each of the following nn rounds, the following two-step process happens:

  1. Alice (either you or the interactor) will output two integers aa and bb (1≤a,b≤31 \le a, b \le 3, a≠ba \neq b) — the colors chosen by Alice.
  2. Bob (either you or the interactor) will output two integers ii and cc (1≤i≤n1 \le i \le n, c=ac = a or c=bc = b) — the vertex and the color chosen by Bob. Vertex ii must be a previously uncolored vertex.

If any of your outputs are invalid, the jury will output "-1" and you will receive a Wrong Answer verdict.

At the end of all nn turns, if you have lost the game, the jury will output "-1" and you will receive a Wrong Answer verdict.

If your program has received a −1-1 instead of a valid value, it must terminate immediately. Otherwise, you may receive an arbitrary verdict because your solution might be reading from a closed stream.

Note that if you are playing as Alice, and there already exists an edge connected two vertices of the same color, the interactor will not terminate early and you will keep playing all nn rounds.

After outputting, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

In this problem, hacks are disabled.

Input

Each test contains multiple test cases. The first line contains a single integer tt (1≤t≤10001 \le t \le 1000) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers nn, mm (1≤n≤1041 \le n \le 10^4, n−1≤m≤min⁡(n⋅(n−1)2,104)n - 1 \le m \le \min(\frac{n \cdot (n - 1)}{2}, 10^4)) — the number of vertices and the number of edges in the graph, respectively.

Each of the next mm lines of each test case contains two integers uiu_i, viv_i (1≤ui,vi≤n1 \le u_i, v_i \le n) — the edges of the graph. It is guaranteed that the graph is connected and there are no multiple edges or self-loops.

It is guaranteed that the sum of nn and the sum of mm over all test cases does not exceed 10410^4.

Sample Input 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
Copy

Sample Output 1

Alice
3 1

1 2

2 1






Bob

1 2

2 1

4 1

3 3
Copy

Note

Note that the sample test cases are example games and do not necessarily represent the optimal strategy for both players.

In the first test case, you choose to play as Alice.

  1. Alice chooses two colors: 33 and 11. Bob chooses vertex 33 and colors it with color 11.
  2. Alice chooses two colors: 11 and 22. Bob chooses vertex 22 and colors it with color 22.
  3. Alice chooses two colors: 22 and 11. Bob chooses vertex 11 and colors it with color 11.

Alice wins because the edge (3,1)(3, 1) connects two vertices of the same color.

In the second test case, you choose to play as Bob.

  1. Alice chooses two colors: 22 and 33. Bob chooses vertex 11 and colors it with color 22.
  2. Alice chooses two colors: 11 and 22. Bob chooses vertex 22 and colors it with color 11.
  3. Alice chooses two colors: 22 and 11. Bob chooses vertex 44 and colors it with color 11.
  4. Alice chooses two colors: 33 and 11. Bob chooses vertex 33 and colors it with color 33.

Bob wins because there are no edges with vertices of the same color.

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 8ms
  4. Powered by Hydro v4.14.1 Community