Trang trại của Farmer John gồm \(N\) đồng cỏ (\(2\leq N\leq 10^5\)) được nối bởi \(N-1\) con đường sao cho có thể đi từ bất kỳ đồng cỏ nào đến bất kỳ đồng cỏ nào khác. Nói cách khác, trang trại là một cây. Nhưng sau 28 năm xử lý những bài toán thuật toán hóc búa chắc chắn nảy sinh từ cây, FJ đã quyết định rằng một trang trại có dạng cây đơn giản là quá phức tạp. Ông tin rằng các bài toán thuật toán sẽ đơn giản hơn trên các đường đi.

Vì vậy, kế hoạch của ông là phân hoạch tập hợp các con đường thành nhiều đường đi và giao trách nhiệm về những đường đi này cho các người làm công xứng đáng. Ông không quan tâm đến số lượng đường đi. Tuy nhiên, ông muốn bảo đảm rằng tất cả các đường đi đều dài nhất có thể, để không người làm công nào có thể dùng những thuật toán kém hiệu quả về mặt tiệm cận mà vẫn thoát tội!

Hãy giúp Farmer John xác định số nguyên dương \(K\) lớn nhất sao cho có thể phân hoạch các con đường thành những đường đi có độ dài ít nhất \(K\).

Phân nhóm

• Trong các test 2-4, cây có dạng hình sao; nhiều nhất một đỉnh có bậc lớn hơn hai.
• Các test 5-8 thỏa mãn \(N\le 10^3\).
• Các test 9-15 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) cách nhau bởi dấu cách, mô tả một cạnh nối đỉnh \(a\) với đỉnh \(b\). Cả \(a\) và \(b\) đều thuộc đoạn \(1\ldots N\).

Dữ liệu ra

In \(K\).

Ví dụ

8
1 2
1 3
1 4
4 5
1 6
6 7
7 8

3

Nguồn

USACO 2020 February Contest, Platinum - Delegation: https://usaco.org/index.php?page=viewproblem2&cpid=1020

Tác giả: Mark Gordon và Dhruv Rohatgi.