题目描述

在云原生分布式服务网格中，存在由$n$个服务节点构成的网络拓扑结构。每个节点需要动态分配不同类型的资源（如计算单元），以确保服务的高效运行。资源分配需满足以下条件：

• ​连通性约束：同一资源类型的任意两个节点之间的通信路径上的所有节点必须分配相同的资源类型。

• 唯一性约束：同一资源类型的任意两个节点的到中心节点的网络跳数(中心节点到该节点距离)必须不同。

系统的调度策略的代价定义为所有资源类型中出现次数最少的那一类型的出现次数。目标是选择一个中心节点，使得该代价最大化。

输入格式

第一行一个整数$t$表示有t组数据

随后每组数据第一行一个整数$n$

随后$n-1$行，每行两个数字$u,v$,表示一个通信路径的两个节点

输出格式

每组数据输出一个整数表示答案

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

4
1
3
3

数据范围

• $1 \leq t \leq 10^4$
• $3 \leq n \leq 2*10^5$,
• $1 \leq u,v \leq n$
• $\sum n \leq 2*10^5$