Problem Description

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.

Input Format

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$.

Output Format

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

4
6
1 6
2 1
3 2
4 3
5 4
6 5
6
1 3
3 5
5 1
2 4
4 6
6 2
3
1 2
2 3
3 1
5
1 4
2 5
3 1
4 2
5 3

2
3
3
3

Hint

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