Chia đường

Tại vương quốc Verde, nổi tiếng với hệ thống giao thông xanh và thông minh, có \(N\) khu vực canh tác được kết nối bằng \(N - 1\) con đường hai chiều. Cấu trúc giao thông hiện tại tạo thành một mạng lưới cây -- tức là luôn tồn tại đúng một đường đi giữa hai khu vực bất kỳ.

Tuy nhiên, sau nhiều năm quản lý và tối ưu hoá mạng lưới, nhà nghiên cứu giao thông trưởng của vương quốc -- ông Hiroshi -- nhận ra rằng hệ thống cây đang dần trở nên phức tạp, khó bảo trì, và không còn hiệu quả trong việc vận hành.

Vì thế, Hiroshi quyết định chia toàn bộ hệ thống con đường thành nhiều đoạn đường liên tiếp, mỗi đoạn là một đường đi ngắn nhất giữa \(2\) đỉnh bất kì. Lưu ý, mỗi con đường trong \(N-1\) con đường thuộc đúng chính xác một đường đi. Mục tiêu của Hiroshi là đảm bảo rằng tất cả các đoạn đường đều có độ dài ít nhất là \(K\), để những người giám sát đoạn đường này không lười biếng và buộc phải làm việc với các đoạn đủ dài.

Hãy giúp Hiroshi tìm giá trị lớn nhất của số nguyên dương \(K\) sao cho có thể chia toàn bộ hệ thống con đường thành một số đoạn mà mỗi đoạn đều có độ dài ít nhất là \(K\).

Input

Dòng đầu tiên chứa số nguyên \(N\) \((2 \le N \le 10^5)\) --- số lượng khu vực.

Mỗi dòng trong \(N - 1\) dòng tiếp theo chứa hai số nguyên \(u\) và \(v\) \((1 \le u, v \le N)\) --- biểu thị có một con đường nối giữa khu vực \(u\) và \(v\).

Output

In ra một số nguyên duy nhất --- độ dài lớn nhất \(K\) thỏa mãn yêu cầu.

Example

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

3

Scoring

• Subtask 1 (20 điểm): \(N \le 100\)
• Subtask 2 (80 điểm): Không có ràng buộc gì thêm.