Беси попала на дальнюю ферму.
Эта ферма состоит из \(N\) амбаров (\(2 \leq N \leq 10^5\)) и \(N-1\) двунаправленных
туннелей между амбарами, так что между любыми двумя амбарами имеется путь, и он
единственный. Каждый амбар, который имеет только один туннель, является выходом.
Когда придёт утро, Беси приземлится на некоторый амбар и попытается достичь выхода.
Но в тот момент, когда Беси приземляется, закон сможет определить ее местоположение.
Некоторые фермеры начнут в различных выходных амбарах и попытаются поймать Беси.
Фермеры двигаются на той же скорости, что и Беси (поэтому в каждый момент времени
каждый фермер может перейти из своего амбара в соседний). Фермеры всё время знают,
где находится Беси, и Беси всё время знает, где находятся фермеры. Фермеры поймают
Беси, если в некоторый момент времени, один из фермеров находится в том же амбаре,
что и Беси или проходит по тому же туннелю, что и Беси. Беси сбежит, если
достигнет амбара с выходом, прежде чем любой из фермеров поймает её.
Беси не уверена в своих шансах на успех, которые зависят от количества
фермеров, которые будут за ней охотиться. Если Вам дан номер амбара \(K\), в
котором приземлится Беси, определите минимальное количество фермеров, которое
необходимо, чтобы поймать Беси, в предположении, что фермеры распределяться
оптимально среди выходных амбаров.
ФОРМАТ ВЫВОДА (файл atlarge.in):
Первая строка ввода содержит \(N\) и \(K\). Каждая из последующих \(N-1\) строк
содержи два целых числа в интервале \(1 \ldots N\), описывающих туннель
между двумя амбарами.
ФОРМАТ ВЫВОДА (файл atlarge.out):
Выведите минимальное количество фермеров, необходимых, чтобы поймать Беси.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 1
1 2
1 3
3 4
3 5
4 6
5 7
|
3
|