Treasure Hunt

There is a maze with n rooms. Between any two rooms, exactly one path exists.

A treasure is hidden in one room. On each question, the searcher chooses one room. If the treasure is in that room, the answer says so. Otherwise, the answer identifies which corridor adjacent to the chosen room must be followed to move toward the treasure.

Given the maze, assume the searcher always chooses questions optimally. Find the minimum number of questions needed to determine the treasure's location in the worst case.

The first line contains the number of rooms n. (1 ≤ n ≤ 50,000)

Each of the next n - 1 lines contains two integers a and b, meaning that rooms a and b are connected by a corridor. Rooms are numbered consecutively from 1 to n.

Print the number of questions needed in the worst case, assuming an optimal strategy.

For the visible test's structure, asking first about room 1, 2, or 3 lets the searcher determine the treasure's location in at most two questions. Asking first about room 4 or 5 makes three questions necessary in the worst case.