Scrooge Minho

Interview

Time limit2sMemory limit512 MB

Summary

Given a tree, place one fire station at the vertex minimizing the maximum distance to any other vertex, and output that distance.

Level: Medium4 of 10
Topics: Tree, Graph, BFS, DFS
Solved: No attempts yet

Problem

Minho, a famously stingy king, rules a country with $N$ cities. To keep the cost of building roads down he built only $N-1$ roads, so between any two cities there is exactly one route.

Minho did not want to pay for several fire stations either, so he decided to build a single fire station in one city. He does pick the best possible city for it. The best position is the city that minimizes the largest distance a fire truck has to travel from that city to reach some other city. Travel inside one city costs nothing, and driving along one road costs a distance of 1.

Given the number of cities and the roads between them, write a program that finds the largest distance a fire truck travels from the fire station built at the best position to reach another city.

Input

The first line contains the number of cities $N$ ( $2 \le N \le 100\,000$ ).

Each of the next $N-1$ lines describes one road. A line contains two integers $u$ and $v$ ( $1 \le u, v \le N$ ) separated by a space, meaning city $u$ and city $v$ are joined by a two-way road. The $N-1$ roads connect all cities into one piece.

Output

Print on the first line the largest distance a fire truck travels from the fire station built at the best position to reach another city.

Examples2

Example 1
Input
```
5
4 5
4 2
2 3
1 2
```
Expected output
```
2
```
Example 2
Input
```
2
1 2
```
Expected output
```
1
```