Когда у Адама появляется корневое дерево (связный неориентированный граф без циклов), он сразу начинает его раскрашивать. Более формально, каждому ребру он сопоставляет некоторый цвет таким образом, чтобы выполнялись два условия:
- Не существует вершины, у которой больше двух инцидентных ребер покрашены в один цвет.
- Для любых двух вершин, у которых есть инцидентные ребра, покрашенные в один цвет (скажем, c), путь между ними содержит ребра только цвета c.
Не все раскраски дерева нравятся Адаму одинаково. Рассмотрим путь от некоторой вершины до корня. Количество различных цветов на этом пути назовем стоимостью вершины. Стоимостью раскраски дерева будем называть максимальную стоимость среди всех вершин дерева. Помогите Адаму определить минимальную стоимость раскраски дерева.
Изначально дерево Адама состоит из одной вершины, которая имеет номер один и является корнем. За один ход Адам подвешивает к уже существующей вершине новую, которая получает номер, равный наименьшему положительному целому не занятому числу. После каждой операции вам нужно сообщать минимальную стоимость раскраски получившегося дерева.
Выходные данные
Выведите n целых чисел — минимальные стоимости раскраски дерева после каждого добавления.
Примечание
На картинке изображен один из возможных вариантов раскраски дерева из примера в самый последний момент. Стоимость вершин с номерами 11 и 12 равна трем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
1 1 1 3 4 4 7 3 7 6 6
|
1 1 1 1 1 2 2 2 2 2 3
|