Sau một ngày làm việc vất vả, anh Long sẽ thưởng cho mình bằng những bữa ăn với những chùm nho mẫu đơn ngon lành. Anh ta có ~n~ trái nho được nối với nhau qua ~n-1~ cành, hai trái nho bất kì luôn được nối với nhau qua chuỗi những cành. Long sẽ có ba bữa ăn trong ngày. Để chuẩn bị cho bữa ăn, anh ta sẽ cắt ~2~ cành cây bất kì để có được ~3~ nhánh nho, mỗi nhánh cho mỗi bữa.

Tuy nhiên anh Long không muốn bất kì bữa ăn nào quá ngọt ngào nên anh ấy quyết định cắt sao cho độ chênh lệch giữa nhánh có nhiều nho nhất và ít nho nhất là nhỏ nhất có thể. Bạn phải giúp anh ấy tìm độ chênh lệch đó.

Input

• Dòng đầu chứa số nguyên ~n~ là số lượng nho. Các trái được đánh số từ ~1 \to n~ với ~1 \le n \le 2.10^5 ).~
• Mỗi dòng trong ~n-1~ dòng còn lại gồm ~2~ số nguyên ~x~ và ~y~ với ~1 ≤ x,y ≤ n~ số hiệu 2 trái nho nối trực tiếp với nhau.

Output

In ra độ chênh lệch tối thiểu giữa đùm có nhiều nho nhất và ít nho nhất.

Sample input 1

4
1 2
2 3
3 4

Sample output 1

1

Sample input 2

6
1 2
1 3
3 4
3 5
5 6

Sample output 2

0