Arman has recently moved to a remote village in the country-side. The map of the village is in the form of a tree, i.e. there are exactly n − 1 roads connecting n intersections of the village such that for every pair of intersections there is a sequence of roads connecting them.
Every morning Arman goes to his office and late at night he gets back home. It is very dark at night and the village roads do not have any lights so Arman is starting to have problems finding his way back home. There are no signs at intersections and he cannot distinguish them from each other. Even his phone is not signalling on the way, and using GPS is not possible. To solve the problem, he has decided to buy a flashlight. Flashlights have different integer beam distances, and a flashlight with a higher beam range costs more. A flashlight with range d reveals the intersections within a distance at most d around the current intersection. All roads of the village have an equal length of 1.
When Arman leaves office towards home, in every intersection of the path he traverses, he makes a decision as explained below.
Arman doesn’t care about walking a little bit longer as long as he knows regardless of his random choices, he will eventually reach home after passing through at most 109 roads. He wants to purchase the cheapest flashlight for that purpose. Please help him find the appropriate flashlight by which he would be able to reach home.
There are multiple test cases in the input. For each input the first line contains an integer n, the number of intersections in the village (2 ≤ n ≤ 30, 000). Next n − 1 lines each contains two integers a, b meaning that there is a road between intersections a and b (1 ≤ a, b ≤ 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 109 roads regardless of his random choices. If Arman does not need any flashlight, print “0”.
7 1 2 2 3 3 7 4 5 5 7 6 7 0