P17014 [GESP202606 Level 7] Coloring

Student Xiao Yang has an undirected graph $G$ with $n$ vertices, where the vertices in $G$ are numbered $1, 2, \dots, n$ in order. Xiao Yang finds that the degree of every vertex in $G$ is $2$. Obviously, there are exactly $n$ edges in $G$. Xiao Yang wants to color the vertices of $G$ so that the two endpoints of any edge have different colors. Xiao Yang wants to know the minimum number of colors needed to color $G$ under this condition.

This problem contains multiple test cases. The first line contains a positive integer $t$, which indicates the number of test cases. For each test case: The first line contains a positive integer $n$, which indicates the number of vertices in the undirected graph $G$. The next $n$ lines each contain two positive integers $u_i, v_i$, representing an undirected edge connecting vertex $u_i$ and vertex $v_i$. Integers are separated by a space. It is guaranteed that there are no multiple edges or self-loops in $G$.

For each test case, output one line with one integer, which is the minimum number of colors needed to color $G$ under the condition.

### Constraints For $40\%$ of the test points, it is guaranteed that $\sum n \le 500$, where $\sum n$ is the sum of $n$ over all test cases in the input. For all test points, it is guaranteed that $1 \le t \le 100$, $3 \le n \le 10^5$, and $\sum n \le 10^5$. It is guaranteed that there are no multiple edges or self-loops in $G$. Translated by ChatGPT 5