You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一棵有 n 个顶点的树∗ 。您可以选择两个顶点 a 和 b 一次，然后删除从 a 到 b 路径上的所有顶点，包括顶点本身。如果选择 a=b ，则只会移除一个顶点。

你的任务是找出从树中移除路径后所能形成的最大连通组件数 † 。

∗ 树是一个没有循环的连通图。

† 一个连通部分是这样一个顶点集合：从任意顶点到集合中的任意其他顶点都有一条沿边的路径(并且不可能到达不属于这个集合的顶点)。

样例

输入

输入的第一行包含一个整数 t ( 1≤t≤1e4 ) -- 测试用例的数量。

每个测试用例的第一行包含一个整数 n ( 2≤n≤2e5 ) -- 树的大小。

接下来的 n−1 行包含两个整数 u 和 v ( 1≤u,v≤n , u≠v )--由一条边连接的顶点。可以保证这些边构成一棵树。

保证所有测试用例中 n 的总和不超过 2e5 。

输出

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

样例

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
3
2
3
4
3

限制

1s, 1024KiB for each test case.