1991E · Coloring Game

Problem: This is an interactive problem.

Consider an undirected connected graph consisting of $n$ vertices and $m$ edges. Each vertex can be colored with one of three colors: $1$, $2$, or $3$. Initially, all vertices are uncolored.

Alice and Bob are playing a game consisting of $n$ 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.

Input Format: Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \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 $n$, $m$ ($1 \le n \le 10^4$, $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 $m$ lines of each test case contains two integers $u_i$, $v_i$ ($1 \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 $n$ and the sum of $m$ over all test cases does not exceed $10^4$.

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: $3$ and $1$. Bob chooses vertex $3$ and colors it with color $1$.
2. Alice chooses two colors: $1$ and $2$. Bob chooses vertex $2$ and colors it with color $2$.
3. Alice chooses two colors: $2$ and $1$. Bob chooses vertex $1$ and colors it with color $1$.

Alice wins because the edge $(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: $2$ and $3$. Bob chooses vertex $1$ and colors it with color $2$.
2. Alice chooses two colors: $1$ and $2$. Bob chooses vertex $2$ and colors it with color $1$.
3. Alice chooses two colors: $2$ and $1$. Bob chooses vertex $4$ and colors it with color $1$.
4. Alice chooses two colors: $3$ and $1$. Bob chooses vertex $3$ and colors it with color $3$.

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