Делегація (Платина)
Ферма фермера Джона складається з 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.