Делегація (Платина)#10605
Ферма фермера Джона складається з пасовищ, з'єднаних n - 1 дорогами так, що будь-яке пасовище доступне з будь-якого іншого пасовища. Іншими словами, ферма утворює дерево. Однак, після 28 років роботи з хитрими алгоритмічними проблемами, які неминуче виникають через дерева, фермер Джон вирішив, що ферма у формі дерева занадто складна. Він вважає, що алгоритмічні задачі простіші на шляхах.
Його план полягає в тому, щоб розділити множину доріг на кілька шляхів і передати відповідальність за кожен шлях своїм гідним господарям ферми. Його не хвилює кількість шляхів. Тим не менш, він хоче переконатися, що всі ці шляхи є якомога більшими, щоб жоден фермер не зміг уникнути асимптотично неефективних алгоритмів!
Допоможіть фермеру Джону визначити найбільше додатне ціле число , щоб дороги можна було розділити на шляхи довжиною не менше .
Перший рядок містить єдине ціле число (2 \le n \le 10^5). Кожен з наступних n - 1 рядків містить два цілі числа і , що позначають ребро між вершинами і . Обидва і знаходяться в діапазоні .
Виведіть значення .
Приклад 1
Один з можливих шляхів має вигляд: 2-1-6-7-8, 3-1-4-5.