Вы — программист, и у вас есть новогоднее дерево (нет, не елка) — дерево из четырех вершин: одна вершина степени три (имеет номер 1), связанная с тремя листами (имеют номера от 2 до 4).

На новый год программисты обычно веселятся, вот и вы решили повеселиться, добавляя вершины в свое дерево. При этом одна операция добавления выглядит следующим образом:

• Сначала выбирается некоторой лист дерева с номером v.
• Обозначим количество вершин в дереве на данный момент переменной n, тогда в дерево добавляются две вершины с номерами n + 1 и n + 2, а также ребро между вершинами v и n + 1 и ребро между вершинами v и n + 2.

Как и полагается, ваша задача не просто промоделировать процесс добавления вершин в дерево, но и после каждой операции добавления выводить диаметр текущего дерева. Вперед, на решение новогодней задачи!