쥐덫

코끼리 덤보에게는 방 $n$개와 통로 $n-1$개로 이루어진 거대한 미로가 있다. 방에는 $1$번부터 $n$번까지 번호가 붙어 있고, 어느 방에서 출발해도 나머지 모든 방에 갈 수 있다. 그런데 미로에 생쥐 한 마리가 숨어들었다. 덤보는 쥐를 몹시 무서워해서 $t$번 방에 쥐덫을 놓았다. 쥐는 덫이 있는 방을 피해 다니므로, 덤보는 쥐를 덫으로 몰아넣을 방법을 따로 세워야 한다.

쥐는 움직일 곳이 없을 때 말고는 쉬지 않고 돌아다닌다. 쥐가 지나간 통로에는 발자국과 배설물이 남아 더러워지고, 쥐는 더러워진 통로를 다시 지나지 않는다. 덤보는 더러워진 통로를 청소하거나 통로를 돌로 막을 수 있다. 통로를 막고 청소해서 쥐가 덫으로 들어가게 만드는 것이 목표인데, 쥐와 한 공간에 있는 것이 몹시 괴로우므로 되도록 적은 횟수로 끝내려 한다.

이 상황은 두 쪽이 겨루는 게임으로 볼 수 있다. 쥐는 덤보의 행동 횟수를 최대로 만들려 하고, 덤보는 최소 횟수로 이기려 한다. 먼저 움직이는 쪽은 덤보다. 자기 차례에 덤보는 더러운 통로 하나를 청소하거나 통로 하나를 막을 수 있다. 막는 통로가 깨끗한지 더러운지는 상관없다. 한 번 막은 통로는 다시 열 수 없다. 아무것도 하지 않고 차례를 넘겨도 되며, 이렇게 넘긴 차례는 행동 횟수로 세지 않는다. 쥐의 차례가 되면 쥐는 지금 있는 방에서 나가는 통로 가운데 깨끗하고 막히지 않은 통로를 하나 골라 그 통로 건너편 방으로 달려간다. 그런 통로가 하나도 없으면 쥐는 움직이지 않는다.

처음에는 모든 통로가 깨끗하고, 쥐는 $m$번 방에, 덫은 $t$번 방에 있으며, 덤보의 차례부터 시작한다. 두 쪽이 모두 최선을 다할 때 덤보가 해야 하는 행동, 즉 청소와 막기를 합한 횟수의 최솟값을 구하라.

첫째 줄에 정수 $n$, $t$, $m$이 공백으로 구분되어 주어진다. 이어지는 $n-1$개의 줄에는 각각 정수 $a$와 $b$가 공백으로 구분되어 주어지며, $a$번 방과 $b$번 방을 잇는 통로가 있다는 뜻이다.

입력 크기가 크다는 점에 유의하라.

덤보가 해야 하는 행동 횟수의 최솟값을 한 줄에 출력한다. 쥐가 처음부터 덫이 있는 방에 있으면, 즉 $m = t$이면 $0$을 출력한다.

• $1 \le n \le 10^6$
• $1 \le t \le n$, $1 \le m \le n$

예제에서 덤보가 네 번 행동해 끝내는 한 가지 진행은 다음과 같다.

• 덤보가 $4$번 방과 $7$번 방 사이의 통로를 막는다.
• 쥐가 $6$번 방으로 이동한다. $4$번 방과 $6$번 방 사이의 통로가 더러워진다.
• 덤보가 $6$번 방과 $8$번 방 사이의 통로를 막는다.
• 쥐가 움직이지 못한다.
• 덤보가 $4$번 방과 $6$번 방 사이의 통로를 청소한다.
• 쥐가 $4$번 방으로 이동한다. $4$번 방과 $6$번 방 사이의 통로가 다시 더러워진다.
• 덤보가 $2$번 방과 $3$번 방 사이의 통로를 막는다.
• 쥐가 $2$번 방으로 이동한다. $2$번 방과 $4$번 방 사이의 통로가 더러워진다.
• 덤보가 아무것도 하지 않는다.
• 쥐는 $1$번 방으로밖에 갈 수 없어 덫에 걸린다.

덤보는 네 번 행동했다.