4040: [GESP202606 七级] 染色
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
小杨同学有一张包含 n 个结点的无向图 G, G 中的结点依次以 1,2,…,n 编号。
小杨同学发现 G 中每个结点的度数都是 2。显然 G 中恰好有 n 条边。
小杨同学想为 G 中的结点染色，使得任意一条边两端的结点都有不同的颜色。
小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为 G 染色。
输入
第一行，一个正整数 ，表示数据组数。
对于每组数据：
第一行，一个正整数 ，表示无向图 中的结点数。
接下来 行，每行两个正整数 ，表示一条连接结点 与 的无向边，整数之间以空格分隔。
保证 中没有重边与自环。
输出
对于每组数据：输出一行，一个整数，表示在满足条件的前提下为 G 染色需要的最少颜色数。
样例输入 复制
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提示
数据范围
对于 的测试点，保证 ， 指每个输入中多组数据的 的总和。
对于所有测试点，保证 ，，。保证 中没有重边与自环。