染⾊

题目描述

⼩杨同学有⼀张包含 个结点的⽆向图 ， 中的结点依次以 编号。 ⼩杨同学发现 中每个结点的度数都是 。显然 中恰好有 条边。 ⼩杨同学想为 中的结点染⾊，使得任意⼀条边两端的结点都有不同的颜⾊。 ⼩杨同学想知道最少需要多少种颜⾊才能在满⾜条件的前提下为 染⾊。

输入格式

本题包含多组数据。 第⼀⾏，⼀个正整数 ，表⽰数据组数。 对于每组数据： 第⼀⾏，⼀个正整数 ，表⽰⽆向图 中的结点数。 接下来 ⾏，每⾏两个正整数 ，表⽰⼀条连接结点 与 的⽆向边，整数之间以空格分隔。 保证 中没有重边与⾃环。

输出格式

对于每组数据：输出⼀⾏，⼀个整数，表⽰在满⾜条件的前提下为 染⾊需要的最少颜⾊数。

样例输入 #1

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

样例输出 #1

2
3
3
3

数据范围

对于 的测试点，保证 ， 指每个输⼊中多组数据的 的总和。 对于所有测试点，保证 ， ， 。保证 中没有重边与⾃环。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。