Flight Planning

NCPC Airways operates flights among $n$ cities, numbered from $1$ to $n$. The airline runs exactly $n-1$ two-way routes, yet from any city you can still reach every other city. Because of this, between any two cities there is exactly one sequence of flights a passenger can take, so the whole network forms a single tree.

Frequent flyers complain that some trips require changing flights too many times. To improve the network while keeping this structure, the airline will cancel exactly one existing route and open exactly one new route, so that the network still connects all $n$ cities using $n-1$ routes. In other words, after the cancellation and the new opening the network must again be a single tree.

Among all such single swaps, find the one that minimizes the maximum number of flights a passenger might have to take between the two most distant cities, and output that minimized maximum.

The input is guaranteed to allow a strict improvement over the original network.

The first line contains an integer $n$ ($4 \le n \le 2500$), the number of cities.

Each of the next $n-1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$), describing a two-way route between cities $a$ and $b$. The given routes connect all cities and form a tree.

Print a single integer: the smallest possible value of the maximum number of flights between any two cities, after cancelling one route and opening one new route.