E. Деревья Пенчика и Хлои
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

До отъезда Пенчика и Хлои в Сингапур оставалось всего несколько часов, и им не терпелось увидеть высоченные деревья в Сингапурском ботаническом саду! Пытаясь сдержать свое волнение, Пенчик смастерил дерево с корнями, чтобы занять Хлою и себя.

У Пенчика есть корневое дерево$$$^{\text{∗}}$$$, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, с вершиной $$$1$$$ в качестве корня. Хлоя может выбрать целое неотрицательное число $$$d$$$, чтобы создать совершенное бинарное дерево$$$^{\text{†}}$$$ глубины $$$d$$$.

Поскольку Пенчик и Хлоя — хорошие друзья, Хлоя хочет, чтобы ее дерево было изоморфно$$$^{\text{‡}}$$$ дереву Пенчика. Чтобы достичь этого, Хлоя может выполнить следующую операцию над своим деревом любое количество раз:

  • Выбрать ребро $$$(u,v)$$$, где $$$u$$$ является родителем $$$v$$$.
  • Удалить вершину $$$v$$$ и все ребра, связанные с $$$v$$$, а затем соединить всех бывших детей $$$v$$$ непосредственно с $$$u$$$.

В частности, операция над ребром $$$(u, v)$$$, где $$$v$$$ — лист, удалит вершину $$$v$$$ без добавления новых ребер.

Поскольку построение совершенного бинарного дерева может занять много времени, Хлоя хочет выбрать минимальное $$$d$$$, такое, чтобы совершенное бинарное дерево глубины $$$d$$$ можно было сделать изоморфным дереву Пенчика с помощью вышеописанной операции. Обратите внимание, что Хлоя не может менять корни деревьев.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем. Родителем вершины $$$v$$$ называется первая вершина на простом пути от $$$v$$$ до корня. У корня нет родителя. Ребенком вершины $$$v$$$ называется любая вершина $$$u$$$, для которой $$$v$$$ является родителем. Листом называется любая вершина, у которой нет детей.

$$$^{\text{†}}$$$Полным бинарным деревом называется корневое дерево, в котором у каждой вершины $$$0$$$ или $$$2$$$ детей. Совершенное бинарное дерево — это полное бинарное дерево, в котором каждый лист находится на одинаковом расстоянии от корня. Глубина такого дерева равна расстоянию от корня до листа.

$$$^{\text{‡}}$$$Два дерева с корнями, равными $$$r_1$$$ и $$$r_2$$$ соответственно, считаются изоморфными, если существует такая перестановка вершин $$$p$$$, что ребро $$$(u, v)$$$ существует в первом дереве тогда и только тогда, когда ребро $$$(p_u, p_v)$$$ существует во втором дереве, и $$$p_{r_1} = r_2$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — количество вершин в дереве Пенчика.

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

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите в отдельной строке одно целое число: минимальную глубину совершенного бинарного дерева Хлои.

Пример
Входные данные
5
6
1 2 2 1 1
15
1 1 2 2 3 3 4 4 5 5 6 6 7 7
5
1 2 2 2
7
1 1 2 1 1 2
10
1 1 1 2 2 2 4 3 3
Выходные данные
2
3
3
3
3
Примечание

В первом наборе входных данных можно создать совершенное бинарное дерево глубины $$$2$$$.

Рассмотрим выполнение операции на ребре $$$AC$$$. Рёбра $$$AC$$$, $$$CF$$$ и $$$CG$$$ удаляются, а рёбра $$$AF$$$ и $$$AG$$$ добавляются.

Полученное дерево изоморфно дереву, заданному на входе. Можно доказать, что никакая последовательность операций над бинарным деревом глубины менее $$$2$$$ не может привести к дереву, изоморфному дереву, заданному на входе.

Во втором наборе входных данных дерево уже изоморфно совершенному бинарному дереву глубины $$$3$$$.