Задано корневое дерево, состоящее из \(n\) вершин. Вершины пронумерованы от \(1\) до \(n\), корень — это вершина \(1\).
Вы можете совершить следующую операцию не более \(k\) раз:
- выбрать ребро \((v, u)\) дерева такое, что \(v\) является родителем \(u\);
- удалить ребро \((v, u)\);
- добавить ребро \((1, u)\) (т. е. сделать \(u\) с его поддеревом ребенком корня).
Высотой дерева называют максимальную глубину среди всех его вершин, а глубина вершины — это количество ребер на пути от корня до нее. Например, глубина вершины \(1\) равна \(0\), так как она — корень, а глубина всех ее детей равна \(1\).
Какую минимальную высоту дерева можно получить?
Выходные данные
На каждый набор входных данных выведите одно число — наименьшая высота дерева, которую можно получить, совершив не более \(k\) операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 1
1 1 2 2
5 2
1 1 2 2
6 0
1 2 3 4 5
6 1
1 2 3 4 5
4 3
1 1 1
|
2
1
5
3
1
|