Делегация (Платина)
Ферма фермера Джона состоит из n пастбищ, соединенных n - 1 дорогами так, что любое пастбище доступно с любого другого пастбища. То есть ферма - это дерево. Но после 28 лет работы с хитрыми алгоритмическими проблемами, которые неизбежно возникают из-за деревьев, ФД решил, что ферма в форме дерева слишком сложна. Он считает, что алгоритмические задачи проще на путях.
Его план состоит в том, чтобы разделить множество дорог на несколько путей и передать ответственность за этот путь своим достойным хозяевам фермы. Его не волнует количество путей. Тем не менее, он хочет убедиться, что все эти пути являются как можно большими, чтобы ни один фермер не смог избежать асимптотически неэффективных алгоритмов!
Помогите фермеру Джону определить наибольшее положительное целое число k, чтобы дороги можно было разделить на пути длиной не менее k.
Входные данные
Первая строка содержит единственное целое число n (2 ≤ n ≤ 10^5). Каждая из следующих n - 1 строк содержит два целых числа a и b, обозначающих ребро между вершинами a и b. Оба a и b находятся в диапазоне 1 .. n.
Выходные данные
Выведите значение k.
Пример
Один из возможных путей имеет вид: 2−1−6−7−8, 3−1−4−5.