Олимпиадный тренинг

Задача 30710. Gnomes and the Lonely Mountain


Задача

Темы:
Dwarves continue to search for the gold of their ancestors in the depths of the Lonely Mountain. The bowels of the Lonely Mountain are n caves, some of which are connected by two-way passages. At the same time, you can get from each cave to any other through passages, and this can be done in the only way.

The dwarves divided into two groups, which began their search from the caves u0 and v0, respectively. The dwarves of each of the units move together. It takes exactly one minute for a squad of gnomes to explore the cave, after which each squad quickly moves along the passage to one of the neighboring caves. At the same time, the gnomes never enter the cave if they or another party have already visited it. Both units never enter the same cave. If at least one of the gnome units cannot move according to these rules, both units immediately stop searching for treasure.

In order to better explore the bowels of the Lonely Mountain, the dwarves want the search to continue as long as possible. Given a map of the caves in the Lonely Mountain and the initial position of the dwarf units, determine the maximum time the treasure hunt can continue.

Input data format
In the first line the number n (2 ≤ n ≤ 200 000) — number of caves in the Lonely Mountain. The next n−1 lines define the passages between the caves. Each line contains the numbers of two caves v and u connected by a passage (1 ≤ v, u ≤ n). The next line contains the numbers of the caves v0 and u0, in which initially there are two squads of gnomes (1 ≤ v0, u0 ≤n, v0 != u0).

Output data format
Print the maximum number of minutes that the treasure hunt can continue.

Enter Output Explanation
6
1 2
23
34
4 5
5 6
4 5
2
8
1 2
23
34
25
5 6
37
78
18
4