Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Два центроида
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано дерево (неориентированный связный ациклический граф), изначально содержащее только вершину $$$1$$$. Будет несколько запросов к данному дереву. В $$$i$$$-м запросе появится вершина $$$i + 1$$$, соединенная с вершиной $$$p_i$$$ ($$$1 \le p_i \le i$$$).

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

Вершина называется центроидом, если ее удаление разбивает дерево на поддеревья с не более чем $$$\lfloor \frac{n}{2} \rfloor$$$ вершин в каждом, где $$$n$$$ — число вершин дерева. Например, центроид следующего дерева равен $$$3$$$, потому что самое большое поддерево после удаления центроида имеет $$$2$$$ вершины.

В следующем дереве вершины $$$1$$$ и $$$2$$$ являются центроидами.

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

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

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

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

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

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

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

Мы можем показать, что ответ всегда существует.

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

На картинках ниже показан четвертый набор входных данных.

После третьего запроса:

В дереве уже есть вершины $$$2$$$ и $$$3$$$ в качестве центроидов, поэтому никаких операций не требуется.

После четвертого запроса:

Добавление вершины $$$x$$$ к дереву делает вершины $$$2$$$ и $$$3$$$ центроидами. Нужна только одна операция.

После пятого запроса:

Добавление к дереву вершин $$$x$$$ и $$$y$$$ делает вершины $$$5$$$ и $$$2$$$ центроидами. Нужны две операции.

После шестого запроса:

Добавление к дереву вершин $$$x$$$, $$$y$$$ и $$$z$$$ делает вершины $$$5$$$ и $$$2$$$ центроидами. Необходимо три операции.