Связный граф без циклов называется деревом. Листом дерева называется любая вершина, которая связана ровно с одной другой вершиной.
Задано дерево из n вершин с корнем в вершине 1. В каждом листе дерева находится один муравей. За одну секунду несколько муравьёв могут одновременно перейти в предка вершины в которой они находятся. Два муравья не могут находиться одновременно в одной вершине, за исключением корня дерева.
Определите наименьшее время за которое все муравьи смогут попасть в корень дерева. Обратите внимание, что исходно муравьи находятся только в листьях дерева.
Выходные данные
Выведите целое число t — наименьшее время, необходимое, чтобы все муравьи попали в корень дерева.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
8 10
8 11
8 12
|
6
|
|
2
|
2
2 1
|
1
|