← 返回题目列表

Codeforces · 1796/E

E. 彩色子图

中文机器翻译题面 查看原题

Monocarp 有一个树,由 $$$n$$$ 个顶点组成。

他将选择一些顶点 $$$r$$$ 并对从 $$$1$$$ 到 $$$n$$$ 的每个顶点 $$$v$$$ 执行以下操作:

- 设置 $$$d_v$$$ 等于从 $$$v$$$ 到 $$$r$$$ 的距离(最短路径上的边数);
- 颜色$$$v$$$一些颜色。

漂亮的着色满足两个条件:

- 对于每对相同颜色的顶点 $$$(v, u)$$$,存在一条从 $$$v$$$ 到 $$$u$$$ 的路径,该路径仅访问相同颜色的顶点;
- 对于每对相同颜色的顶点 $$$(v, u)$$$, $$$d_v \neq d_u$$$。

请注意,Monocarp 可以选择他想要使用的任意数量的不同颜色。

对于每种使用的颜色,他然后计算该颜色的顶点数。树的成本是这些数字中的最小值。

树的最大成本是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

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

接下来的 $$$n-1$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$) - 边的描述。

给定的边形成一棵树。所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 树的最大可能成本。

示例

输入 #1

4
4
1 2
2 3
3 4
5
1 2
1 3
1 4
1 5
3
1 3
3 2
7
3 2
2 5
7 5
3 1
1 6
1 4

输出 #1

4
1
3
3