Hazzu vừa mới chuyển tới sống trong một thành phố có dạng cây~^\dagger~, bao gồm ~n~ điểm giao và ~n - 1~ con đường hai chiều nối các điểm giao lại với nhau. Để khám phá thành phố thì vào mỗi buổi sáng, Hazzu thường hay chọn một tuyến đường dài nhất (bao gồm các con đường liên tiếp nhau) trong thành phố và chạy bộ từ đầu tới cuối tuyến đường đó. Một khi đã chạy trên tuyến đường nào, Hazzu chỉ chạy qua một con đường đúng một lần.

Thành phố trong ví dụ, bao gồm ~5~ điểm giao và ~4~ con đường nối giữa các điểm giao

Để buổi chạy bộ trở nên thú vị hơn, Hazzu thường chọn tuyến đường chứa một con đường mà anh ấy chưa chạy qua bao giờ. Điều này giúp anh ấy khám phố thành phố mình sống một cách nhanh hơn. Hazzu muốn biết có bao nhiêu tuyến đường dài nhất khác nhau~^\ddagger~ để anh ấy có thể chạy bộ mỗi ngày một cách thú vị.

~\dagger~ Cây là một đồ thị mà trong đó hai đỉnh bất kì đều được nối với nhau bằng đúng một đường đi.

~\ddagger~ Hai tuyến đường dài nhất được gọi là khác nhau khi tồn tại một con đường ở tuyến đường này mà không tồn tại con đường này ở tuyến đường kia.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ (~1 \le n \le 10^6~) là số điểm giao trong thành phố.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u~ và ~v~ đại diện cho con đường hai chiều nối điểm giao thứ ~u~ và điểm giao thứ ~v~.

Output

• Dòng duy nhất số nguyên dương là số tuyến đường dài nhất khác nhau.

Scoring

• Subtask 1 (50% số điểm): ~1 \le \ n \le 10^3~
• Subtask 2 (50% số điểm): ~1 \le \ n \le 10^6~

Samples

Sample Input

5
1 2
2 3
3 4
3 5

Sample Output

2

Notes

• Thành phố ở trong ví dụ, độ dài của tuyến đường dài nhất là ~3~.
• Số lượng tuyến đường dài nhất là ~2~, bao gồm:
  • ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~
  • ~1 \rightarrow 2 \rightarrow 3 \rightarrow 5~