D1 Tree Coloring (Easy Version)

好的，这是根据您的要求翻译和格式化的题面：

D1. Tree Coloring (Easy Version)

时间限制：每次测试 2 秒
内存限制：每次测试 512 兆字节

问题描述

这是问题的简单版本。版本之间的区别在于，在这个版本中，您只需要找到最少的操作次数。只有解决了此问题的所有版本，您才能进行 hack。

您得到一棵有根树*，它由编号为 $1$ 到 $n$ 的 $n$ 个顶点组成，其中根节点的索引为 $1$，且每个顶点最初都是白色的。定义 $d_i$ 为从根节点到第 $i$ 个顶点的距离。您可以执行任意次数的以下操作： - 选择一个白色顶点子集 $S$，使得 $S$ 中任意两个节点之间没有边相连，或者到节点 $1$ 的距离不同。形式化地，对于所有 $x, y \in S$ 且 $x \ne y$，应满足 $d_x \ne d_y$ 并且 $x$ 和 $y$ 之间没有边。 - 将 $S$ 中的顶点涂成黑色。

您的工作是找出将整棵树涂黑所需的最少操作次数。

* 树是一个没有环的连通图。有根树是一种有一个特殊顶点（称为根）的树。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) —— 树中的顶点数。

接下来的 $n-1$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) —— 表示第 $i$ 条边的两个端点。

保证给定的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，在新的一行输出最少操作次数。

样例输入

10
5
3 1
1 2
5 1
4 1
5
3 2
2 4
2 5
1 2
5
3 4
4 1
5 1
1 2
5
2 5
3 1
2 1
3 4
5
1 3
1 5
4 3
2 4
13
2 1
3 2
4 2
5 4
6 3
7 1
8 5
9 6
10 4
11 7
12 8
13 10
10
5 7
8 1
1 10
2 8
8 4
9 4
6 1
5 3
7 8
10
7 6
3 7
6 9
7 1
9 8
5 1
3 10
9 2
1 4
10
10 6
2 8
4 10
7 5
1 2
7 10
10 9
9 1
7 3
10
6 8
9 7
4 10
5 9
4 2
3 8
6 5
1 5
1 10

样例输出

5
4
4
3
3
3
4
4
4
3

样例说明

在第一个测试用例中，$d_1=1$ 且 $d_2=d_3=d_4=d_5=2$。我们可以证明至少需要进行 $5$ 次操作，因为没有两个节点可以同时操作。

在第二个测试用例中，我们可以证明将整棵树涂黑所需的最少操作次数是 $4$。一种方法是：在同一次操作中将节点 $1$ 和 $3$ 涂黑，然后在各自的单次操作中将所有其他 $3$ 个节点涂黑。