Вам дано неориентированное дерево, состоящее из \(n\) вершин.
Назовём вершину листом, если она соединена ровно с одной другой вершиной.
Под расстоянием между двумя вершинами будем понимать количество рёбер на кратчайшем пути между этими вершинами.
Назовем некоторое множество листьев красивым, если максимальное расстояние между любой парой листьев из этого множества не превышает \(k\).
Перед вами стоит задача разделить все листья дерева на непересекающиеся красивые множества. Определите минимальное количество множеств, которые можно получить в результате описанного разделения.
Выходные данные
Выведите минимальное количество красивых множеств в разбиении всех листьев.
Примечание
Картинка описывает разбиение дерева из первого примера.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 3
1 2
1 3
2 4
2 5
3 6
6 7
6 8
3 9
|
2
|
|
2
|
5 3
1 2
2 3
3 4
4 5
|
2
|
|
3
|
6 1
1 2
1 3
1 4
1 5
1 6
|
5
|