Treasure Hunt in the Cave System

The cave system contains n chambers connected by tunnels such that there is a unique path between any two chambers (i.e. the graph is a tree). Hansel hides a treasure in one of the chambers but does not reveal its location. When Gretel asks whether a particular chamber contains the treasure, if her guess is correct Hansel confirms it; if her guess is wrong, he tells her which adjacent chamber is in the direction of the treasure (i.e. the unique neighbor lying on the path to the treasure).

With full information about the cave system provided, determine the minimum number of queries Gretel must make in the worst case in order to find the treasure, no matter where Hansel hides it.

Hint: If Gretel chooses a chamber v to query and if the treasure is not there, Hansel effectively indicates the unique neighbor along the path toward the treasure. Hence, if Gretel starts with a carefully chosen chamber, she will have to ask queries one per chamber along the path from v to the treasure. In other words, if she selects a starting chamber whose maximum distance to any other chamber is minimized, then the worst‐case number of queries equals that minimum maximum distance plus one. This minimum maximum distance is known as the radius of the tree. Formally, if the diameter of the tree is \(d\), then the radius is given by \(r=\lceil d/2\rceil\) and the answer is \(r+1\).

More formally, if the treasure is at a chamber at distance \(d_v\) from the chosen chamber, then the number of queries required is \(d_v+1\). Optimizing over all choices of the starting chamber gives the answer \(\min_{v\in V}(\max_{u\in V}\,dist(v,u)) + 1 = r+1\).

inputFormat

The first line contains a single integer \(n\) (\(1\le n\le 10^5\)), the number of chambers. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), representing a tunnel connecting chamber \(u\) and chamber \(v\). It is guaranteed that there is exactly one unique path between any two chambers.

outputFormat

Output a single integer: the minimum number of queries required in the worst case to guarantee that the treasure is found.

Explanation: If the chosen starting chamber has a maximum distance \(r\) to any other chamber, then the worst-case scenario is \(r+1\) queries.

sample

1

1