Phân Công Đường Đi

Có $N$ đỉnh tạo thành một cây với $N-1$ cạnh. Cần phân hoạch tập cạnh thành các đường đi (path) trong cây sao cho mỗi cạnh thuộc đúng một đường đi.

Mục tiêu: tối đa hóa $K$ — độ dài tối thiểu của các đường đi trong phân hoạch — tức là tìm $K$ lớn nhất sao cho tồn tại cách phân hoạch với mọi đường đi có độ dài $\ge K$.

Dữ liệu vào

• Dòng 1: số nguyên $N$ ($2\le N\le {10}^5$)
• $N-1$ dòng tiếp theo: mỗi dòng hai số $a$ và $b$ mô tả cạnh nối đỉnh $a$ và $b$

Dữ liệu ra

In ra $K$ — giá trị lớn nhất của độ dài đường đi tối thiểu.

Ràng buộc

• $2\le N\le {10}^5$

Ví dụ