CF1453E.Dog Snacks

Gildong is playing with his dog, Badugi. They're at a park that has $n$ intersections and $n-1$ bidirectional roads, each $1$ meter in length and connecting two intersections with each other. The intersections are numbered from $1$ to $n$, and for every $a$ and $b$ ($1 \le a, b \le n$), it is possible to get to the $b$-th intersection from the $a$-th intersection using some set of roads.

Gildong has put one snack at every intersection of the park. Now Gildong will give Badugi a mission to eat all of the snacks. Badugi starts at the $1$-st intersection, and he will move by the following rules:

• Badugi looks for snacks that are as close to him as possible. Here, the distance is the length of the shortest path from Badugi's current location to the intersection with the snack. However, Badugi's sense of smell is limited to $k$ meters, so he can only find snacks that are less than or equal to $k$ meters away from himself. If he cannot find any such snack, he fails the mission.
• Among all the snacks that Badugi can smell from his current location, he chooses a snack that minimizes the distance he needs to travel from his current intersection. If there are multiple such snacks, Badugi will choose one arbitrarily.
• He repeats this process until he eats all $n$ snacks. After that, he has to find the $1$-st intersection again which also must be less than or equal to $k$ meters away from the last snack he just ate. If he manages to find it, he completes the mission. Otherwise, he fails the mission.

Unfortunately, Gildong doesn't know the value of $k$. So, he wants you to find the minimum value of $k$ that makes it possible for Badugi to complete his mission, if Badugi moves optimally.

吉尔东正在和他的狗巴杜吉玩耍。他们身处一个拥有 $n$ 个路口和 $n-1$ 条双向道路的公园中，每条道路长度均为 $1$ 米，并连接两个不同的路口。路口编号为 $1$ 至 $n$，且对任意 $a$ 和 $b$（$1 \le a, b \le n$），总存在若干条道路使得可以从第 $a$ 个路口到达第 $b$ 个路口。

吉尔东已在公园的每个路口放置了一份零食。现在，吉尔东将给巴杜吉一项任务：吃掉所有零食。巴杜吉从第 $1$ 个路口出发，并遵循以下规则移动：

• 巴杜吉寻找距离自己最近的零食。此处“距离”定义为从巴杜吉当前所在路口到含有零食的路口之间的最短路径长度。然而，巴杜吉的嗅觉范围限制为 $k$ 米，因此他仅能发现距离自身不超过 $k$ 米的零食。若他无法发现任何此类零食，则任务失败。
• 在巴杜吉当前可嗅探到的所有零食中，他选择一个使其从当前位置出发所需行走距离最小的零食。若存在多个满足该条件的零食，巴杜吉可任选其一。
• 他不断重复此过程，直至吃掉全部 $n$ 份零食。此后，他必须再次找到第 $1$ 个路口，且该路口与他刚吃完的最后一份零食所在的路口之间的距离也必须不超过 $k$ 米。若他成功找到，则任务完成；否则任务失败。

不幸的是，吉尔东并不知道 $k$ 的值。因此，他希望你找出能使巴杜吉在最优移动策略下成功完成任务的最小 $k$ 值。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of intersections of the park.

The next $n-1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) each, which means there is a road between intersection $u$ and $v$. All roads are bidirectional and distinct.

It is guaranteed that:

• For each test case, for every $a$ and $b$ ($1 \le a, b \le n$), it is possible to get to the $b$-th intersection from the $a$-th intersection.
• The sum of $n$ in all test cases doesn't exceed $2 \cdot 10^5$.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $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$），表示交叉路口 $u$ 与 $v$ 之间存在一条道路。所有道路均为双向且互不相同。

保证满足以下条件：

• 对于每个测试用例，任意 $a$ 和 $b$（$1 \le a, b \le n$），均可从第 $a$ 个交叉路口到达第 $b$ 个交叉路口；
• 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the minimum possible value of $k$ such that Badugi can complete the mission.

对于每个测试用例，输出一个整数——使得 Badugi 能够完成任务的最小可能的 $k$ 值。

In the first case, Badugi can complete his mission with $k=2$ by moving as follows:

1. Initially, Badugi is at the $1$-st intersection. The closest snack is obviously at the $1$-st intersection, so he just eats it.
2. Next, he looks for the closest snack, which can be either the one at the $2$-nd or the one at the $3$-rd intersection. Assume that he chooses the $2$-nd intersection. He moves to the $2$-nd intersection, which is $1$ meter away, and eats the snack.
3. Now the only remaining snack is on the $3$-rd intersection, and he needs to move along $2$ paths to get to it.
4. After eating the snack at the $3$-rd intersection, he needs to find the $1$-st intersection again, which is only $1$ meter away. As he gets back to it, he completes the mission.

In the second case, the only possible sequence of moves he can make is $1$ – $2$ – $3$ – $4$ – $1$. Since the distance between the $4$-th intersection and the $1$-st intersection is $3$, $k$ needs to be at least $3$ for Badugi to complete his mission.

In the third case, Badugi can make his moves as follows: $1$ – $5$ – $6$ – $7$ – $8$ – $2$ – $3$ – $4$ – $1$. It can be shown that this is the only possible sequence of moves for Badugi to complete his mission with $k=3$.

在第一种情况下，Badugi 可以通过 $k=2$ 完成任务，具体移动过程如下：

1. 最初，Badugi 位于第 $1$ 个路口。显然，距离最近的零食就在第 $1$ 个路口，因此他直接吃掉它。
2. 接着，他寻找距离最近的零食，该零食可能位于第 $2$ 个路口，也可能位于第 $3$ 个路口。假设他选择了第 $2$ 个路口。他移动到第 $2$ 个路口（距离为 $1$ 米），并吃掉那里的零食。
3. 此时，唯一剩余的零食位于第 $3$ 个路口，他需要沿 $2$ 条路径前往该处。
4. 吃掉第 $3$ 个路口的零食后，他需要再次找到第 $1$ 个路口，而该路口仅距他 $1$ 米。当他返回第 $1$ 个路口时，任务即告完成。

在第二种情况下，他唯一可能的移动序列为 $1$ – $2$ – $3$ – $4$ – $1$。由于第 $4$ 个路口与第 $1$ 个路口之间的距离为 $3$，因此 $k$ 至少需为 $3$，Badugi 才能完成任务。

在第三种情况下，Badugi 的移动可如下进行：$1$ – $5$ – $6$ – $7$ – $8$ – $2$ – $3$ – $4$ – $1$。可以证明，这是 Badugi 在 $k=3$ 条件下完成任务的唯一可能移动序列。