Ratatöskr

Time limit2sMemory limit512 MB

Summary

Two ravens hunt a squirrel on a tree, moving one raven per signal while the squirrel slips along branches. Find the fewest signals needed to capture it.

Level: Medium7 of 10
Topics: Game theory, Graph, BFS
Solved: No attempts yet

Problem

Ratatöskr is a squirrel that lives in a giant (but finite) mythical tree called Yggdrasil. He likes to gossip, which sets the other inhabitants of the tree against each other. Ratatöskr is therefore hunted by the two ravens of Odin, Hugin and Munin, who want to bring him to justice.

The tree is made up of nodes connected by branches. Initially, the ravens and the squirrel sit on three different nodes. Then the following happens repeatedly:

On Odin's signal, one of the ravens launches into the air and flies to another node of the tree (or possibly back to its previous position), while the other stays where it is.
During this maneuver, Ratatöskr can travel along the branches to reach another node, but may not pass through a node where a raven sits. He is much quicker than the ravens and will reach his destination before the flying raven lands.

Ratatöskr gets captured if one of the ravens flies to his position and there is no other node he can escape to.

Help Odin determine an optimal strategy for capture, that is, the minimum number of signals he has to give until Ratatöskr is guaranteed to be captured by a raven. If Ratatöskr can escape them indefinitely, output impossible.

Input

The input consists of:

one line with a single integer $n$ ( $3 \le n \le 80$ ), the number of nodes in the tree. The nodes are labeled $1, \ldots, n$ .
one line with a single integer $r$ ( $1 \le r \le n$ ), the initial position of the squirrel Ratatöskr.
one line with a single integer $h$ ( $1 \le h \le n$ ), the initial position of the raven Hugin.
one line with a single integer $m$ ( $1 \le m \le n$ ), the initial position of the raven Munin.
$n-1$ lines each containing two integers $i$ and $j$ ( $1 \le i < j \le n$ ), indicating a branch between nodes $i$ and $j$ .

The positions $r$ , $h$ and $m$ are distinct. There is at most one branch between any two nodes, and every node is reachable from every other node by a sequence of branches.

Output

One line containing an integer $s$ , the number of signals that the ravens need to capture Ratatöskr in an optimal strategy. If Ratatöskr can escape them indefinitely, output impossible.

Examples2

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