{"zh":"<div class=\"water\">\r\n\r\n# 染⾊\r\n\r\n#### 题目描述\r\n⼩杨同学有⼀张包含 个结点的⽆向图 ， 中的结点依次以 编号。\r\n⼩杨同学发现 中每个结点的度数都是 。显然 中恰好有 条边。\r\n⼩杨同学想为 中的结点染⾊，使得任意⼀条边两端的结点都有不同的颜⾊。\r\n⼩杨同学想知道最少需要多少种颜⾊才能在满⾜条件的前提下为 染⾊。\r\n\r\n#### 输入格式\r\n本题包含多组数据。\r\n第⼀⾏，⼀个正整数 ，表⽰数据组数。\r\n对于每组数据：\r\n第⼀⾏，⼀个正整数 ，表⽰⽆向图 中的结点数。\r\n接下来 ⾏，每⾏两个正整数 ，表⽰⼀条连接结点 与 的⽆向边，整数之间以空格分隔。\r\n保证 中没有重边与⾃环。\r\n\r\n#### 输出格式\r\n对于每组数据：输出⼀⾏，⼀个整数，表⽰在满⾜条件的前提下为 染⾊需要的最少颜⾊数。\r\n\r\n#### 样例输入 #1\r\n\r\n4\r\n6\r\n1 6\r\n2 1\r\n3 2\r\n4 3\r\n5 4\r\n6 5\r\n6\r\n1 3\r\n3 5\r\n5 1\r\n2 4\r\n4 6\r\n6 2\r\n3\r\n1 2\r\n2 3\r\n3 1\r\n5\r\n1 4\r\n2 5\r\n3 1\r\n4 2\r\n5 3\r\n\r\n\r\n#### 样例输出 #1\r\n\r\n2\r\n3\r\n3\r\n3\r\n\r\n\r\n#### 数据范围\r\n对于 的测试点，保证 ， 指每个输⼊中多组数据的 的总和。\r\n对于所有测试点，保证 ， ， 。保证 中没有重边与⾃环。\r\n\r\n#### 知识点与难度\r\n本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。\r\n\r\n---\r\n\r\n### 测试点分布\r\n\r\n| Subtask | 分值 | 测试点编号 | 说明 |\r\n|:-------:|:----:|:----------:|:-----|\r\n| 0 | 10 | 1~2 | 样例 |\r\n| 1 | 20 | 3~8 | 小规模 / 特殊性质 |\r\n| 2 | 15 | 9~11 | Hack |\r\n| 3 | 30 | 12~20 | 中大规模 |\r\n| 4 | 25 | 21~25 | 随机回归 |\r\n\r\n> 生测试数据后，按实际 subtask 分组改写上表。\r\n\r\n</div>\r\n"}