Một đất nước có \(n\) thành phố được đánh số từ \(1\) tới \(n\) và có \(n - 1\) con đường hai chiều. Ta có thể du lịch giữa hai thành phố bất kỳ bằng cách đi qua các con đường.

Khoảng cách giữa hai thành phố \(x\) và \(y\) được xác định là số các con đường cần phải đi qua khi đi từ \(x\) đến \(y\).

Các công ty du lịch mong muốn trong một chuyến đi du lịch, khách hàng có thể đi qua càng nhiều thành phố càng tốt.
Do vậy, nhà quản lý quyết định phá hủy một con đường và xây dựng mới một con đường khác (vẫn đảm bảo việc đi lại giữa hai thành phố bất kỳ bằng cách đi qua các con đường), với mục đích khoảng cách giữa hai thành phố phải đi qua nhiều con đường nhất là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên gồm số nguyên \(n\) (3 \le n \le 300000), số lượng các thành phố
• \(n - 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u\) và \(v\), biểu thị con đường hai chiều kết nối thành phố \(u\) và \(v\) \((1 \le u, v \le n)\)

Dữ liệu ra:

• Ghi khoảng cách lớn nhất giữa hai thành phố phải đi qua nhiều con đường nhất sau khi thực hiện phép thay đổi đúng một con đường (xóa một, thêm một) và vẫn giữ đồ thị liên thông.

Input 1

6
1 2
2 3
2 5
4 5
5 6

Output 1

5

Giải thích

• Ta phá hủy con đường \((2,5)\) và xây mới con đường \((3,4)\). Khi đó khoảng cách lớn nhất giữa hai thành phố \(1\) và \(6\) là \(5\).

Chú ý:

• 20% số điểm ứng với \(n \le 100\)
• 20% số điểm ứng với \(n \le 3000\)
• 20% số điểm ứng với \(n \le 300000\), có nhiều nhất một thành phố thỏa mãn có từ 3 con đường trở lên kết nối với nó
• 40% số điểm còn lại không có giới hạn gì thêm