eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Автотуризм

Автотуризм

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

В Байтландии существуют n городов, соединённых n - 1 дорогами с двусторонним движением таким образом, что из каждого города можно проехать в любой другой по сети дорог. Длина каждой дороги равна 1 километру.

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

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

В первой строке заданы два целых числа n и m (2 n 500000, 1 m 200000000) - количество городов в стране и количество километров, которое автомобиль может проехать без дозаправки. В последующих n - 1 строках описаны дороги. Каждая дорога задаётся двумя целыми числами a и b (1 a, b n) - номерами городов, которые она соединяет. Длина каждой дороги равна 1 км.

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

Выведите максимальное количество городов, которое можно посетить без дозаправки.

Пример

Входные данные #1
7 7
2 4
1 2
5 6
6 7
2 3
6 1
Выходные данные #1
6

Примечание

5 городов можно посетить, например, по схеме 4 → 5 → 7 → 5 → 6 → 5 → 2 или по схеме 3 → 2 → 1 → 2 → 5 → 6 → 5.

Источник 2012 Харьков, Зимняя школа, День Сергея Копеловича, Задача I