Ферма Джона состоит из \(N\) пастбищ (\(1 \leq N \leq 10^5\)), соединённых
\(N-1\) дорогой, так что любое пастбище достижимо из любого другого.
То есть ферма представляет собой дерево.
ФД хочет разбить множество дорог на несколько путей. Его не беспокоит количество
путей. Однако он хочет чтобы все эти пути максимально возможными.
Помогите ФД определить максимальное положительное целое \(K\) такое, что
дороги могут быть разделены на пути длины не менее \(K\).
ОЦЕНИВАНИЕ:
- В тестах 2-4 дерево формирует звезду; не более чем одна вершина имеет степень больше чем 2.
- В тестах 5-8 \(N\le 10^3\).
- В тестах 9-15 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл deleg.in):
Первая строка содержит
\(N\).
Каждая из следующих \(N-1\) строк содержит по два целых числа \(a\) и \(b\),
описывающих ребро между вершинами \(a\) и \(b\). Оба числа \(a\) и \(b\) в интервале \(1 \ldots N\).
ФОРМАТ ВЫВОДА (файл deleg.out):
Выведите \(K\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1 2
1 3
1 4
4 5
1 6
6 7
7 8
|
3
|