← 返回题目列表

Codeforces · 1453/E

E. 狗零食

中文机器翻译题面 查看原题

Gildong 正在和他的狗 Badugi 玩耍。他们所在的公园有 $$$n$$$ 十字路口和 $$$n-1$$$ 双向道路,每条道路长 $$$1$$$ 米,并将两个十字路口相互连接。交叉路口的编号从 $$$1$$$ 到 $$$n$$$,对于每个 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$),可以使用一些道路从第 $$$a$$$ 个交叉路口到达第 $$$b$$$ 个交叉路口。

Gildong 在公园的每个路口都放置了一份小吃。现在吉尔东会给巴杜吉一个任务,让他吃掉所有的零食。 Badugi 从 $$$1$$$-st 交叉路口开始,他将按照以下规则移动:

- 巴杜吉寻找离他尽可能近的零食。这里,距离是从Badugi当前位置到小吃路口的最短路径的长度。然而Badugi的嗅觉仅限于$$$k$$$米,所以他只能找到距离自己小于等于$$$k$$$米的零食。如果他找不到任何这样的零食,他的任务就失败了。
- 在巴杜吉当前位置可以闻到的所有零食中,他选择了一种能最大程度地缩短他从当前十字路口行驶的距离的零食。如果有多种这样的零食,巴杜吉会任意选择一种。
- 他重复这个过程,直到吃完所有 $$$n$$$ 零食。之后,他必须再次找到 $$$1$$$-st 路口,该路口距离他刚刚吃的最后一顿零食也必须小于或等于 $$$k$$$ 米。如果他能找到它,他就完成了任务。否则他的任务就失败了。

不幸的是,Gildong 不知道 $$$k$$$ 的值。因此,他希望您找到 $$$k$$$ 的最小值,如果 Badugi 移动最佳,则使 Badugi 能够完成他的任务。

输入

每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - $$$k$$$ 的最小可能值,以便 Badugi 可以完成任务。

示例

输入 #1

3
3
1 2
1 3
4
1 2
2 3
3 4
8
1 2
2 3
3 4
1 5
5 6
6 7
5 8

输出 #1

2
3
3

注意

在第一种情况下,Badugi 可以通过如下移动以 $$$k=2$$$ 完成他的任务:

1. 最初,Badugi 位于$$$1$$$-st 交叉路口。最近的小吃显然在$$$1$$$-st 路口,所以他就吃了。
2. 接下来,他寻找最近的零食,可以是位于 $$$2$$$-nd 的零食,也可以是位于 $$$3$$$-rd 交叉路口的零食。假设他选择 $$$2$$$-nd 交叉点。他走到 $$$1$$$ 米外的第 $$$2$$$-nd 十字路口,吃零食。
3. 现在唯一剩下的零食就在$$$3$$$-rd路口,他需要沿着$$$2$$$路径移动才能到达。
4. 在$$$3$$$-rd路口吃完零食后,他需要再次找到$$$1$$$-st路口,距离只有$$$1$$$米。当他回来时,他就完成了任务。

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

在第三种情况下,Badugi 可以采取如下行动:$$$1$$$ – $$$5$$$ – $$$6$$$ – $$$7$$$ – $$$8$$$ – $$$2$$$ – $$$3$$$ – $$$4$$$ – $$$1$$$。可以证明,这是Badugi 以$$$k=3$$$ 完成其任务的唯一可能的动作序列。