6220 - 染色
题目描述
小杨同学有一张包含 n 个结点的无向图 G，结点依次以 1,2,\ldots,n 编号。
小杨发现 G 中每个结点的度数都是 2。显然 G 中恰好有 n 条边。
小杨想给 G 中的结点染色，使得任意一条边两端的结点都有不同的颜色。请问在满足条件的前提下，最少需要多少种颜色才能给 G 染色。
输入
本题包含多组数据。
第一行，一个正整数 t，表示数据组数。
对于每组数据：第一行，一个正整数 n，表示无向图 G 中的结点数。
接下来 n 行，每行两个正整数 u_i,v_i，表示一条连接结点 u_i 与 v_i 的无向边。
保证 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
说明
数据范围
对于 40% 的测试点，保证 \sum n \le 500。对于所有测试点，保证 1 \le t \le 100，3 \le n \le 10^5，\sum n \le 10^5，且 G 中没有重边与自环。
标签
