Задача D. Травля тараканов ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Произошло ужасное — в квартире доктора Шелдона Купера завелись тараканы! Пока все насекомые не будут убиты, Шелдон не успокоится.

Чтобы вычислить тараканьи гнезда, Шелдон поймал одного таракана. Проведя эксперимент, доктор выяснил, что этот таракан является разведчиком, а значит посещает все гнезда. Установив на таракане маленький передатчик, Шелдон отпустил его.

Проследив путь таракана в течении нескольких часов доктор узнал всю информацию о гнездах и путях между ними. Оказалось, что количество гнезд равно n, а между каждой парой гнезд существует ровно один тараканий путь. Таким образом, все пути образуют дерево, в вершинах которого располагаются гнезда, соединенные неориентированными ребрами — отрезками пути.

Шелдон вундеркинд, и еще в девять лет выяснил, что каждый таракан за день по своей любопытности посетит все гнезда, которое находится не более, чем в k отрезках пути от гнезда, в котором он этот день начал. Также Шелдон считает, что до его действий в каждом гнезде есть хотя бы один таракан.

После сбора всей информации, Шелдон хочет заразить некоторые гнезда ядом так, чтобы каждый таракан в течении следующего дня побывал хотя бы в одном зараженном гнезде. Для экономного использования яда, Шелдон написал программу, которая вычисляет наименьшее число гнезд, которые необходимо заразить.

Сможете ли Вы написать такую программу?

Решения, работающие для n ≤ 18, будут оцениваться из 40 баллов.

Решения, работающие для n ≤ 10 000, будут оцениваться из 70 баллов.

Формат входного файла

В первой строке входного файла содержатся целые числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 100) — количество гнезд и наибольшее разрешенное расстояние от гнезда до ближайшего зараженного.

Следующие n − 1 строк содержат описание ребер дерева. Каждая строка содержит описание одного ребра — номера гнезд, которые соединяет это ребро. Гнезда нумеруются целыми числами от 1 до n.

Формат выходного файла

В выходной файл выведите единственное целое число — наименьшее число гнезд, которые необходимо заразить.

Примеры тестов

1 1

1

3 1
1 2
2 3

1

3 0
1 2
2 3

3