Тимофей приехал в известную летнюю школу и нашел там дерево на \(n\) вершинах. Дерево — это связный неориентированный граф без циклов.
Каждая вершина этого дерева, кроме \(c_0\), покрашена в белый цвет. Вершина \(c_0\) покрашена в черный цвет.
Тимофей хочет покрасить все вершины этого дерева в черный цвет. Для этого он выполняет \(n - 1\) операцию. Во время \(i\)-й операции он выбирает белую вершину \(c_i\) и красит ее в черный цвет.
Назовем позитивностью дерева минимальное расстояние между всеми парами различных черных вершин в нем. Расстоянием между вершинами \(v\) и \(u\) называется количество ребер на пути от \(v\) до \(u\).
После каждой очередной покраски Тимофей хочет знать позитивность текущего дерева.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке \(n - 1\) число.
Число с номером \(i\) должно быть равно позитивности дерева, полученного первыми \(i\) покрасками.
Примечание
В первом наборе входных данных, после второй покраски, дерево выглядит так: 
Расстояние между вершинами \(1\) и \(6\) равно \(3\), расстояние между вершинами \(4\) и \(6\) равно \(3\), расстояние между вершинами \(1\) и \(4\) равно \(2\). Позитивность такого дерева равна минимуму из этих расстояний, то есть \(2\).
В третьем наборе входных данных, после четвертой покраски, дерево выглядит так: 
Позитивность такого дерева равна \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
6 6
4 1 3 5 2
2 4
6 5
5 3
3 4
1 3
4 2
4 1 3
3 1
2 3
1 4
10 3
10 7 6 5 2 9 8 1 4
1 2
1 3
4 5
4 3
6 4
8 7
9 8
10 8
1 8
7 3
7 5 1 2 4 6
1 2
3 2
4 5
3 4
6 5
7 6
9 7
9 3 1 4 2 6 8 5
4 1
8 9
4 8
2 6
7 3
2 4
3 5
5 4
10 2
1 8 5 10 6 9 4 3 7
10 7
7 8
3 6
9 7
7 6
4 2
1 6
7 5
9 2
|
3 2 1 1 1
3 1 1
3 2 2 2 2 2 1 1 1
4 2 2 1 1 1
5 1 1 1 1 1 1 1
4 3 2 2 1 1 1 1 1
|