Ирис любит полные бинарные деревья.
Определим глубину корневого дерева как максимальное количество вершин на простых путях от некоторой вершины до корня. Полное бинарное дерево глубины \(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\). Можете ли вы сказать ей ответ?
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел, \(i\)-е из которых представляет бинарную глубину дерева, образованного первыми \(i\) вершинами.
Примечание
В первом наборе входных данных итоговое дерево показано ниже:
- Дерево, состоящее из вершины \(1\), имеет бинарную глубину \(1\) (само дерево является полным бинарным деревом глубины \(1\)).
- Дерево, состоящее из вершин \(1\) и \(2\), имеет бинарную глубину \(2\) (мы можем добавить вершину \(3\), чтобы сделать его полным бинарным деревом глубины \(2\)).
- Дерево, состоящее из вершин \(1\), \(2\) и \(3\), имеет бинарную глубину \(2\) (само дерево является полным бинарным деревом глубины \(2\)).
Во втором наборе входных данных полное бинарное дерево, образованное после добавления некоторых вершин к дереву, состоящему из \(n\) вершин, показано ниже (добавленные вершины выделены жирным):
Глубина образованного полного бинарного дерева равна \(4\).
В пятом наборе входных данных итоговое дерево показано ниже:
Можно доказать, что Ирис не может сформировать никакое полное бинарное дерево, добавляя вершины и рёбра, поэтому бинарная глубина равна \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|