도망친 소

결국 궁지에 몰린 베시는 외딴 농장의 땅속으로 숨었다. 농장에는 헛간이 $N$개 ($2 \leq N \leq 10^5$) 있고, 헛간을 잇는 양방향 굴이 $N-1$개 있어서 어느 두 헛간 사이에도 경로가 정확히 하나씩 있다. 굴이 하나만 연결된 헛간은 출구다. 아침이 되면 베시는 어느 헛간에서 땅 위로 올라와 출구에 도달하려 한다.

베시가 땅 위로 올라오는 순간 경찰은 베시의 위치를 정확히 파악한다. 그러면 농부 여러 명이 출구 헛간에서 출발해 베시를 잡으러 온다. 농부의 이동 속도는 베시와 같다. 즉 한 시간 단위마다 각 농부는 인접한 헛간으로 한 칸 움직인다. 농부는 베시의 위치를 항상 알고 베시도 농부의 위치를 항상 안다. 어느 순간이든 농부가 베시와 같은 헛간에 있거나 같은 굴을 지나고 있으면 베시는 잡힌다. 반대로 잡히기 전에 출구 헛간에 도달하면 베시는 탈출한다. 베시가 출구 헛간에서 올라오는 경우도 있다. 그때는 그 헛간에서 출발하는 농부가 베시가 올라오는 순간 같은 헛간에 있으므로 베시는 잡힌다.

베시가 빠져나갈 수 있을지는 경찰이 투입할 수 있는 농부 수에 달려 있다. 베시가 헛간 $K$에서 올라온다고 할 때, 농부들이 출구 헛간에 최적으로 나뉘어 배치된다고 가정하고 베시를 잡는 데 필요한 농부의 최소 인원을 구하라.

첫째 줄에 $N$과 $K$가 주어진다 ($1 \leq K \leq N$). 다음 $N-1$개 줄에는 각각 $1$ 이상 $N$ 이하의 정수 두 개가 주어지며, 두 헛간을 잇는 굴 하나를 나타낸다.

베시를 반드시 잡는 데 필요한 농부의 최소 인원을 출력한다.