D. Сбросить k ребер
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано корневое дерево, состоящее из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$, корень — это вершина $$$1$$$.

Вы можете совершить следующую операцию не более $$$k$$$ раз:

  • выбрать ребро $$$(v, u)$$$ дерева такое, что $$$v$$$ является родителем $$$u$$$;
  • удалить ребро $$$(v, u)$$$;
  • добавить ребро $$$(1, u)$$$ (т. е. сделать $$$u$$$ с его поддеревом ребенком корня).

Высотой дерева называют максимальную глубину среди всех его вершин, а глубина вершины — это количество ребер на пути от корня до нее. Например, глубина вершины $$$1$$$ равна $$$0$$$, так как она — корень, а глубина всех ее детей равна $$$1$$$.

Какую минимальную высоту дерева можно получить?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le n - 1$$$) — количество вершин в дереве и наибольшее количество операций, которые вы можете совершить.

Во второй строке записаны $$$n-1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$) — родитель $$$i$$$-й вершины. Вершина $$$1$$$ — корень.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно число — наименьшая высота дерева, которую можно получить, совершив не более $$$k$$$ операций.

Пример
Входные данные
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