← 返回题目列表

Codeforces · 2050/G

G. 树木破坏

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

给定一棵树$$$^{\text{*}}$$$,具有 $$$n$$$ 个顶点。您可以选择两个顶点 $$$a$$$ 和 $$$b$$$ 一次,并删除从 $$$a$$$ 到 $$$b$$$ 的路径上的所有顶点,包括顶点本身。如果选择$$$a=b$$$,则只会删除一个顶点。

你的任务是找到从树中删除路径后可以形成的最大连通分量$$$^{\text{†}}$$$。

输入

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

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

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由边连接的顶点。保证边形成一棵树。

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

输出

对于每个测试用例,输出一个整数——使用所描述的操作可以实现的最大连接组件数。

示例

输入 #1

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

输出 #1

1
3
2
3
4
3