Two Postmen

Interview

Time limit1sMemory limit128 MB

Summary

Split the edges of a tree rooted at node 1 between two postmen starting at the root so the later finishing time is minimized.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, DFS, Greedy
Solved: No attempts yet

Problem

A village has just opened a brand-new post office. It hired two postmen who, every morning, set out from the post office and deliver letters throughout the village. You must plan their routes so that the last letter is delivered as early as possible.

The village has $n$ houses numbered from $1$ to $n$ . The post office is house $1$ . The houses are joined by $n-1$ two-way roads, and this road network lets you travel between any two houses (that is, the network forms a tree). Traversing a single road takes a postman $1$ minute.

Both postmen start at the post office (house $1$ ), and every house must receive its letter. Each road only needs to be traveled by at least one of the two postmen. A postman does not need to return to the post office after finishing. The time at which the last letter is delivered is the later of the two postmen's finishing times, and the goal is to make this value as small as possible.

Input

The first line contains an integer $n$ , the number of houses in the village ( $1 \le n \le 3000$ ).

Each of the next $n-1$ lines describes one road. A line contains two integers $a$ and $b$ , meaning there is a road connecting house $a$ and house $b$ ( $1 \le a, b \le n$ ).

Output

Print, on a single line, the minimum number of minutes in which the two postmen can deliver all the letters.

Examples2

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