Вам задано дерево (неориентированный связный ациклический граф), изначально содержащее только вершину \(1\). Будет несколько запросов к данному дереву. В \(i\)-м запросе появится вершина \(i + 1\), соединенная с вершиной \(p_i\) (\(1 \le p_i \le i\)).
После каждого запроса найдите наименьшее количество операций, необходимых для того, чтобы текущее дерево имело два центроида. За одну операцию вы можете добавить одну вершину и одно ребро к дереву так, чтобы оно осталось деревом.
Вершина называется центроидом, если ее удаление разбивает дерево на поддеревья с не более чем \(\lfloor \frac{n}{2} \rfloor\) вершин в каждом, где \(n\) — число вершин дерева. Например, центроид следующего дерева равен \(3\), потому что самое большое поддерево после удаления центроида имеет \(2\) вершины.
В следующем дереве вершины \(1\) и \(2\) являются центроидами.
Выходные данные
Для каждого набора входных данных выведите \(n - 1\) целое число. \(i\)-е число является ответом на \(i\)-й запрос — наименьшее количество операций, необходимых для того, чтобы текущее дерево имело два центроида.
Мы можем показать, что ответ всегда существует.
Примечание
На картинках ниже показан четвертый набор входных данных.
После третьего запроса:
В дереве уже есть вершины
\(2\) и
\(3\) в качестве центроидов, поэтому никаких операций не требуется.
После четвертого запроса:
Добавление вершины
\(x\) к дереву делает вершины
\(2\) и
\(3\) центроидами. Нужна только одна операция.
После пятого запроса:
Добавление к дереву вершин
\(x\) и
\(y\) делает вершины
\(5\) и
\(2\) центроидами. Нужны две операции.
После шестого запроса:
Добавление к дереву вершин
\(x\),
\(y\) и
\(z\) делает вершины
\(5\) и
\(2\) центроидами. Необходимо три операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|