e-olymp
Соревнования

2018 USACO January

Корова в опасности (Золото)

Загнанная в угол, Бесси ушла в дальнюю ферму. Ферма состоит из n сараев и n - 1 двунаправленных туннелей так, что между каждой парой сараев имеется уникальный путь. Каждый сарай, в котором есть только один туннель, является выходом. Когда наступит утро, Бесси появится в каком-то сарае и попытается добраться до выхода.

Но как только Бесси появится на поверхности, представители закона смогут определить ее местонахождение. Затем некоторые фермеры будут пытаться поймать Бесси у различных выходных сараев. Фермеры движутся с той же скоростью, что и Бесси (поэтому на каждом шаге каждый фермер может перемещаться из одного сарая в соседний сарай). Фермеры всегда знают, где находится Бесси, а Бесси всегда знает, где находятся фермеры. Фермеры словят Бесси, если в некоторый момент фермер оказывается в том же сарае, что и Бесси, или пересекает тот же туннель, что и Бесси. И наоборот, Бесси сбегает, если достигает выходного сарая до того, как ее поймают фермеры.

Бесси не уверена в своих шансах на успех, которые зависят от количества фермеров, которых может задействовать закон. Учитывая, что Бесси всплывает в сарае k, помогите Бесси определить минимальное количество фермеров, которое потребуется, чтобы поймать Бесси, при условии, что фермеры оптимально распределятся между выходными сараями.

Входные данные

Первая строка содержит n (2n105) и k. В каждой из следующих n - 1 строк заданы два целых числа, каждое в диапазоне 1 .. n, описывающие туннель между двумя сараями.

Выходные данные

Выведите минимальное количество фермеров, необходимых для поимки Бесси.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
7 1
1 2
1 3
3 4
3 5
4 6
5 7
Выходные данные #1
3
Источник 2018 USACO Январь, Золото