Codeforces Round 688 (Div. 2) |
---|
Finished |
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:
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.
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, print one integer — the minimum possible value of $$$k$$$ such that Badugi can complete the mission.
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
2 3 3
In the first case, Badugi can complete his mission with $$$k=2$$$ by moving as follows:
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$$$.
Name |
---|