CF1796E.Colored Subgraphs

Monocarp has a tree, consisting of $n$ vertices.

He is going to select some vertex $r$ and perform the following operations on each vertex $v$ from $1$ to $n$:

• set $d_v$ equal to the distance from $v$ to $r$ (the number of edges on the shortest path);
• color $v$ some color.

A nice coloring satisfies two conditions:

• for each pair of vertices of the same color $(v, u)$, there exists a path from $v$ to $u$ that only visits vertices of the same color;
• for each pair of vertices of the same color $(v, u)$, $d_v \neq d_u$.

Note that Monocarp can choose any amount of different colors he wants to use.

For each used color, he then counts the number of vertices of this color. The cost of the tree is the minimum of these numbers.

What can be the maximum cost of the tree?

Monocarp 有一棵由 $n$ 个顶点构成的树。

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

• 将 $d_v$ 设为 $v$ 到 $r$ 的距离（即最短路径上的边数）；
• 给 $v$ 染上某种颜色。

一种“优美的染色”（nice coloring）需满足两个条件：

• 对于任意一对同色顶点 $(v, u)$，存在一条仅经过同色顶点的从 $v$ 到 $u$ 的路径；
• 对于任意一对同色顶点 $(v, u)$，有 $d_v \neq d_u$。

注意：Monocarp 可以使用任意数量的不同颜色。

对每种被使用的颜色，他统计该颜色所染的顶点数。该树的“代价”（cost）定义为所有这些数量中的最小值。

该树可能达到的最大代价是多少？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

Each of the next $n-1$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$) — the description of an edge.

The given edges form a tree. The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each testcase print a single integer — the maximum possible cost of the tree.

对于每个测试用例，输出一个整数——树可能的最大代价。