Задано корневое дерево, состоящее из \(n\) вершин. Вершины пронумерованы от \(1\) до \(n\), корень — это вершина \(1\).
Вы можете совершить следующую операцию не более \(k\) раз:
Высотой дерева называют максимальную глубину среди всех его вершин, а глубина вершины — это количество ребер на пути от корня до нее. Например, глубина вершины \(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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач