C. Заражение дерева
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дано корневое дерево из $$$n$$$ вершин. Вершина $$$1$$$ — корень. Изначально все вершины здоровы.

Каждую секунду вы делаете две операции: распространение и, после этого, инъекцию:

  1. Распространение: для каждой вершины $$$v$$$, если хотя бы один ребёнок $$$v$$$ заражён, то вы можете распространить инфекцию, дополнительно заразив не более одного ребёнка $$$v$$$ на свой выбор.
  2. Инъекция: вы можете выбрать одну любую здоровую вершину и заразить её.

Этот процесс повторяется каждую секунду до тех пор, пока всё дерево не будет заражено. Необходимо найти минимальное время в секундах, за которое можно заразить всё дерево.

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

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

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

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

Гарантируется, что данный граф является деревом.

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

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

Для каждого набора входных данных выведите одно число — минимальное время в секундах, за которое можно заразить всё дерево.

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

На картинке изображено дерево из первого набора входных данных в каждую секунду.

Вершина покрашена в чёрный, если она не заражена. Вершина покрашена в синий, если она заражена инъекцией в течение последней прошедшей секунды. Вершина покрашена в зелёный, если она заражена распространением в течение последней прошедшей секунды. Вершина покрашена в красный, если она заражена, но не в течение последней прошедшей секунды.

Обратите внимание, что вы можете выбирать, какие именно вершины будут заражены распространением и инъекциями.