E. Полное бинарное дерево Ирис
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Ирис любит полные бинарные деревья.

Определим глубину корневого дерева как максимальное количество вершин на простых путях от некоторой вершины до корня. Полное бинарное дерево глубины $$$d$$$ — это бинарное дерево глубины $$$d$$$ с ровно $$$2^d - 1$$$ вершинами.

Ирис называет дерево $$$d$$$-бинарным, если к нему можно добавить некоторые вершины и рёбра, чтобы оно стало полным бинарным деревом глубины $$$d$$$. Обратите внимание, что любая вершина может быть выбрана в качестве корня полного бинарного дерева.

Поскольку выполнение операций над большими деревьями затруднительно, она определяет бинарную глубину дерева как минимальное $$$d$$$, удовлетворяющее условию, что дерево является $$$d$$$-бинарным. В частности, если не существует целого числа $$$d \ge 1$$$, такого что дерево является $$$d$$$-бинарным, то бинарная глубина дерева равна $$$-1$$$.

У Ирис сейчас есть дерево, состоящее только из вершины $$$1$$$. Она хочет добавить ещё $$$n - 1$$$ вершин, чтобы сформировать большее дерево. Она будет добавлять вершины по одной. Когда она добавляет вершину $$$i$$$ ($$$2 \leq i \leq n$$$), она сообщит вам целое число $$$p_i$$$ ($$$1 \leq p_i < i$$$) и добавит новое ребро, соединяющее вершины $$$i$$$ и $$$p_i$$$.

Ирис хочет спросить вас о бинарной глубине дерева, образованного первыми $$$i$$$ вершинами для всех $$$1 \le i \le n$$$. Можете ли вы сказать ей ответ?

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

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

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

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

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

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

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

Пример
Входные данные
7
3
1 1
6
1 2 3 4 5
7
1 1 3 2 5 1
10
1 1 2 1 4 2 4 5 8
10
1 1 3 1 3 2 2 2 6
20
1 1 2 2 4 4 5 5 7 6 8 6 11 14 11 8 13 13 12
25
1 1 3 3 1 5 4 4 6 8 11 12 8 7 11 13 7 13 15 6 19 14 10 23
Выходные данные
1 2 2 
1 2 2 3 3 4 
1 2 2 3 3 4 4 
1 2 2 3 3 3 4 4 5 5 
1 2 2 3 3 4 4 4 -1 -1 
1 2 2 3 3 4 4 4 4 5 5 5 5 6 6 6 6 6 6 7 
1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8
Примечание

В первом наборе входных данных итоговое дерево показано ниже:

  • Дерево, состоящее из вершины $$$1$$$, имеет бинарную глубину $$$1$$$ (само дерево является полным бинарным деревом глубины $$$1$$$).
  • Дерево, состоящее из вершин $$$1$$$ и $$$2$$$, имеет бинарную глубину $$$2$$$ (мы можем добавить вершину $$$3$$$, чтобы сделать его полным бинарным деревом глубины $$$2$$$).
  • Дерево, состоящее из вершин $$$1$$$, $$$2$$$ и $$$3$$$, имеет бинарную глубину $$$2$$$ (само дерево является полным бинарным деревом глубины $$$2$$$).

Во втором наборе входных данных полное бинарное дерево, образованное после добавления некоторых вершин к дереву, состоящему из $$$n$$$ вершин, показано ниже (добавленные вершины выделены жирным):

Глубина образованного полного бинарного дерева равна $$$4$$$.

В пятом наборе входных данных итоговое дерево показано ниже:

Можно доказать, что Ирис не может сформировать никакое полное бинарное дерево, добавляя вершины и рёбра, поэтому бинарная глубина равна $$$-1$$$.