Copil Copac получил список из \(n-1\) ребра, описывающих дерево на \(n\) вершинах. Он решил нарисовать его, используя следующий алгоритм:
- Шаг \(0\): Рисует первую вершину (вершину \(1\)). Переходит к шагу \(1\).
- Шаг \(1\): Для каждого ребра из входных данных в порядке ввода: если ребро соединяет уже нарисованную вершину \(u\) с не нарисованной вершиной \(v\), он рисует \(v\) и ребро. После прохода по всем рёбрам он переходит к шагу \(2\).
- Шаг \(2\): Если все вершины нарисованы, завершает алгоритм. Иначе переходит к шагу \(1\).
Количество проходов определяется как количество раз, которое Copil Copac выполняет шаг \(1\).
Найдите количество проходов, необходимых Copil Copac для рисования дерева.
Выходные данные
Для каждого набора входных данных выведите количество проходов, необходимых Copil Copac для рисования дерева.
Примечание
В первом наборе входных данных:
После первого прохода дерево будет выглядеть так:
После второго прохода:
Таким образом, Copil Copac нужно \(2\) прохода, чтобы нарисовать дерево.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6
4 5
1 3
1 2
3 4
1 6
7
5 6
2 4
2 7
1 3
1 2
4 5
|
2
3
|