C1. Мейпл и красота дерева (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на $$$t$$$ и $$$n$$$ ниже. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Мейпл дано корневое дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, где корень имеет индекс $$$1$$$. Каждая вершина дерева помечена либо нулем, либо единицей. К сожалению, Мейпл забыла, как помечены вершины, и только помнит, что есть ровно $$$k$$$ нулей и $$$n - k$$$ единиц.

Для каждой вершины определим имя вершины как двоичную строку, образованную конкатенацией меток вершин от корня до вершины. Более формально, $$$\text{name}_1 = \text{label}_1$$$ и $$$\text{name}_u = \text{name}_{p_u} + \text{label}_u$$$ для всех $$$2\le u\le n$$$, где $$$p_u$$$ — родитель вершины $$$u$$$, а $$$+$$$ обозначает собой конкатенацию строк.

Красота дерева равна длине наибольшей общей подпоследовательности$$$^{\text{∗}}$$$ имен всех листьев$$$^{\text{†}}$$$. Ваша задача — определить максимальную красоту среди всех возможных распределений меток на дереве с ровно $$$k$$$ нулями и $$$n - k$$$ единицами.

$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях. Наибольшая общая подпоследовательность строк $$$s_1, s_2, \ldots s_m$$$ — это самая длинная строка, которая является подпоследовательностью всех $$$s_1, s_2, \ldots, s_m$$$.

$$$^{\text{†}}$$$Листом называется любая вершина, у которой нет детей.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 1000$$$, $$$0 \leq k \leq n$$$) — количество вершин и количество вершин, помеченных нулем, соответственно.

Вторая строка содержит $$$n - 1$$$ целых чисел $$$p_2, p_3, \ldots, p_{n}$$$ ($$$1 \leq p_i \le i - 1$$$) — родитель вершины $$$i$$$.

Обратите внимание, что на сумму $$$n$$$ по всем наборам входных данных нет дополнительных ограничений.

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

Для каждого набора входных данных выведите одно целое число, представляющее максимальную красоту среди всех возможных распределений меток на дереве с ровно $$$k$$$ нулями и $$$n - k$$$ единицами.

Примеры
Входные данные
5
7 3
1 1 2 2 3 3
7 2
1 1 2 3 1 1
5 0
1 2 3 4
5 2
1 1 1 1
5 4
1 1 1 1
Выходные данные
3
2
5
1
2
Входные данные
5
2 0
1
2 1
1
3 0
1 1
3 1
1 2
3 1
1 1
Выходные данные
2
2
2
3
2
Примечание
В первом наборе входных данных максимальная красота равна $$$3$$$, когда вершины помечены как $$$[0, 0, 0, 1, 1, 1, 1]$$$, и наибольшая общая подпоследовательность равна 001.
Во втором наборе входных данных максимальная красота равна $$$2$$$, когда вершины помечены как $$$[1, 0, 0, 1, 1, 1, 1]$$$, и наибольшая общая подпоследовательность равна 11.