Вы — программист, и у вас есть новогоднее дерево (нет, не елка) — дерево из четырех вершин: одна вершина степени три (имеет номер 1), связанная с тремя листами (имеют номера от 2 до 4).
На новый год программисты обычно веселятся, вот и вы решили повеселиться, добавляя вершины в свое дерево. При этом одна операция добавления выглядит следующим образом:
- Сначала выбирается некоторой лист дерева с номером v.
- Обозначим количество вершин в дереве на данный момент переменной n, тогда в дерево добавляются две вершины с номерами n + 1 и n + 2, а также ребро между вершинами v и n + 1 и ребро между вершинами v и n + 2.
Как и полагается, ваша задача не просто промоделировать процесс добавления вершин в дерево, но и после каждой операции добавления выводить диаметр текущего дерева. Вперед, на решение новогодней задачи!
Выходные данные
Выведите q целых чисел — диаметр текущего дерева после каждой операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
3
4
8
5
|
3
4
4
5
6
|