Gnomes and the Lonely Mountain

Time limit2sMemory limit512 MB

Summary

Two gnome groups start at two nodes of a tree and walk to unvisited nodes without ever colliding; find the longest number of minutes the search can last.

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

Problem

Gnomes keep searching for their ancestors' gold in the depths of the Lonely Mountain. The caves there number $n$ , and some of them are joined by two-way passages. From every cave, any other cave can be reached through the passages, and there is exactly one way to do so.

Two gnome groups start their search from caves $u_0$ and $v_0$ . Each group moves together. A group spends exactly one minute examining its cave, then quickly moves through a passage to one of the neighboring caves. A group never enters a cave that it or the other group has already visited. The two groups never enter the same cave. If at least one group cannot move under these rules, both groups stop searching immediately.

The gnomes want the search to last as long as possible. Given the map of the caves and the starting positions of the groups, find the maximum number of minutes the search can continue.

Input

The first line contains $n$ ( $2 \le n \le 200\,000$ ), the number of caves. Each of the next $n - 1$ lines contains two cave numbers $v$ and $u$ connected by a passage ( $1 \le v, u \le n$ ). The last line contains the starting caves $v_0$ and $u_0$ of the two groups ( $1 \le v_0, u_0 \le n$ , $v_0 \ne u_0$ ).

Output

Print the maximum number of minutes the search can continue.

Examples2

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