#P17891. Lice Hopping

Lice Hopping

给定一棵有 nn 个结点的树。你可以从任意结点出发,每次跳到与当前位置距离不超过 dd 的另一个结点。树上距离为简单路径上的边数。

要求每个结点恰好作为起点或某次跳跃的落点出现一次。跳跃途中经过的结点不算访问,也不影响它以后作为落点。

求能够访问全部结点的最小整数 dd。

输入格式

第一行测试用例数 tt,1≤t≤2×1051\le t\le2\times10^5。

每组第一行整数 nn,2≤n≤1062\le n\le10^6。接着 n−1n-1 行各包含两个整数 u,vu,v,表示一条边,1≤u,v≤n1\le u,v\le n,u≠vu\ne v。输入保证是一棵树。

所有测试用例的 nn 之和不超过 10610^6。

输出格式

每组输出一个整数,表示最小的 dd。

样例

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

第一组可按 3→1→23\to1\to2 访问。第四组可按

8,9,4,2,10,11,5,1,6,12,13,3,15,7,148,9,4,2,10,11,5,1,6,12,13,3,15,7,14

访问,相邻落点的树上距离均不超过 22。