술래잡기

지은이는 술래잡이 게임 중에 마침내 구석에 몰리게 되어 외딴 농장에 숨었습니다. 농장은 $N$ 개의 헛간($2 \leq N \leq 10^5$)과 헛간 사이에 $N-1$ 개의 양방향 터널로 구성되어 있어, 모든 헛간 쌍 사이에는 고유한 경로가 있습니다. 터널이 하나뿐인 모든 헛간은 출구입니다. 아침이 오면, 지은이는 어느 헛간에서든지 표면으로 올라와 출구에 도달하려고 시도할 것입니다.

하지만 지은이가 표면으로 올라오는 순간,술래들은 그녀의 위치를 정확하게 파악할 수 있습니다. 그런 다음 일부 술래들이 다양한 출구 헛간에서 출발해서 지은이를 잡으려고 시도합니다. 술래들은 지은이와 같은 속도로 움직입니다(따라서 각 시간마다 술래는 한 헛간에서 인접한 헛간으로 이동할 수 있습니다). 술래들은 지은이가 어디에 있는지 항상 알고 있고, 지은이는 술래들이 어디에 있는지 항상 알고 있습니다. 만약 어느 순간에 술래가 지은이와 같은 헛간에 있거나, 지은이와 같은 터널을 건너고 있다면, 그들은 지은이를 잡습니다. 반대로, 지은이는 그녀를 잡으려는 술래들보다 먼저 출구 헛간에 도착하면 탈출합니다.

지은이는 투입할 수 있는 술래의 수에 따라 성공 여부가 결정되기 때문에 그녀의 성공 가능성에 대해 확신할 수 없습니다. 지은이가 헛간 $K$에서 표면으로 올라온다면, 술래들이 출구 헛간 중에서 최적으로 배치된다는 가정 하에 지은이를 잡기 위해 필요한 최소한의 술래 수를 베시가 결정하도록 도와주세요.

지은이를 잡기 위해 필요한 최소한의 농부 수를 출력해주세요.