Getting Back Home

Arman recently moved to a remote village in the countryside. The map of the village is a tree: exactly $n-1$ roads connect $n$ intersections, and every pair of intersections is joined by a sequence of roads.

Every morning Arman goes to his office, and late at night he gets back home. Nights are very dark and the village roads have no lights, so Arman has started to have trouble finding his way back home. The intersections carry no signs and he cannot tell them apart. His phone has no signal on the way either, so GPS is not possible. To solve the problem he decided to buy a flashlight. Flashlights have different integer beam distances, and a flashlight with a longer beam costs more. A flashlight with range $d$ reveals every intersection within distance at most $d$ of the current intersection. All roads of the village have the same length 1.

When Arman leaves the office towards home, he makes a decision at every intersection of the path he traverses.

1. If he sees home, he just moves towards it.
2. Assume he is at intersection $u$. Let $A$ be the set of all roads incident to $u$. Let $B$ be the empty set at the initial time, and $\{e\}$ otherwise, where $e$ is the road he just arrived at $u$ through. Let $C$ be the set of useless roads incident to $u$. A road $e'$ incident to $u$ is called useless if all simple paths starting at $u$ and passing through $e'$ have length less than $d$. If $A - (B \cup C)$ is not empty, one road of this set is chosen randomly. Otherwise the road $e$ is chosen again.

Arman does not mind walking a little bit longer as long as he knows that, regardless of his random choices, he will eventually reach home after passing through at most $10^9$ roads. He wants to purchase the cheapest flashlight for that purpose. Find the smallest beam range by which he is able to reach home.

There are multiple test cases in the input. The first line of each test case contains an integer $n$, the number of intersections in the village ($2 \le n \le 30000$). Each of the next $n-1$ lines contains two integers $a$ and $b$, meaning that there is a road between intersections $a$ and $b$ ($1 \le a, b \le n$). Arman's home is at intersection 1 and his office is at intersection $n$. The input terminates with a line containing 0, which should not be processed.

For each test case, output a single line containing the minimum range $d$ of a flashlight that guarantees Arman can always reach home after passing through at most $10^9$ roads, regardless of his random choices. If Arman does not need any flashlight, print 0.