Ratatöskr

Ratatöskr는 거대하지만 유한한 신화 속 나무 Yggdrasil에 사는 다람쥐이다. 그는 수다를 떨기 좋아하고, 그 때문에 나무의 다른 주민들이 서로 적대하게 된다. 그래서 Odin의 까마귀 Hugin과 Munin이 그를 잡아 심판에 넘기려고 쫓는다.

나무는 가지로 이어진 노드들로 이루어져 있다. 처음에 까마귀 두 마리와 다람쥐는 서로 다른 세 노드에 앉아 있다. 이후 다음 과정이 반복된다.

• Odin의 신호가 떨어지면 까마귀 한 마리가 날아올라 나무의 다른 노드로 날아간다(또는 이전 위치로 되돌아갈 수도 있다). 나머지 한 마리는 제자리에 머문다.
• 이 동작이 진행되는 동안 Ratatöskr는 가지를 따라 다른 노드로 이동할 수 있다. 단, 까마귀가 앉아 있는 노드는 지나갈 수 없다. 그는 까마귀보다 훨씬 빨라서 날아가는 까마귀가 착지하기 전에 목적지에 도착한다.

까마귀 중 하나가 Ratatöskr의 위치로 날아왔는데 그가 달아날 수 있는 다른 노드가 없으면 그는 잡힌다.

Odin이 잡는 최적의 전략을 찾도록 도와라. 즉, Ratatöskr가 까마귀에게 반드시 잡히기까지 Odin이 내려야 하는 신호의 최소 횟수를 구하라. 그가 무한히 도망칠 수 있다면 impossible을 출력하라.

입력은 다음과 같다.

• 한 줄에 정수 $n$ ($3 \le n \le 80$)이 주어진다. 나무의 노드 수이다. 노드는 $1, \ldots, n$으로 번호가 매겨진다.
• 한 줄에 정수 $r$ ($1 \le r \le n$)이 주어진다. 다람쥐 Ratatöskr의 초기 위치이다.
• 한 줄에 정수 $h$ ($1 \le h \le n$)이 주어진다. 까마귀 Hugin의 초기 위치이다.
• 한 줄에 정수 $m$ ($1 \le m \le n$)이 주어진다. 까마귀 Munin의 초기 위치이다.
• $n-1$개의 줄에 각각 정수 $i$와 $j$ ($1 \le i < j \le n$)가 주어진다. 노드 $i$와 $j$를 잇는 가지가 있다는 뜻이다.

$r$, $h$, $m$은 서로 다르다. 두 노드를 잇는 가지는 최대 하나이며, 모든 노드는 가지를 따라 다른 모든 노드에 도달할 수 있다.

한 줄에 정수 $s$를 출력한다. 최적 전략에서 까마귀가 Ratatöskr를 잡는 데 필요한 신호의 횟수이다. Ratatöskr가 무한히 도망칠 수 있다면 impossible을 출력한다.