Sau một ngày làm việc vất vả, Phát sẽ thưởng cho mình bằng những bữa ăn với những trái ớt ngon lành.

Anh ta có ~n~ trái ớt được nối với nhau qua ~n-1~ cành, hai trái ớt bất kì luôn được nối với nhau qua chuỗi những cành. Tóm lại, những trái ớt đó tạo thành cây.

Phát sẽ có ba bữa ăn trong ngày. Để chuẩn bị cho bữa ăn, anh ta sẽ cắt hai cành cây bất kì để có được ba đùm ớt, mỗi đùm cho mỗi bữa.

Tuy nhiên Phát không muốn bất kì bữa ăn nào quá cay, nên anh ấy quyết định cắt sao cho độ chênh lệch giữa đùm có nhiều ớt nhất và ít nhất là nhỏ nhất.

Yêu cầu: Hãy tìm độ chênh lệch nhỏ nhất có thể.

Input

• Dòng đầu chứa số nguyên ~n~ là số lượng ớt. Các trái ớt được đánh số từ ~1~ đến ~n~;

• Mỗi dòng trong ~n-1~ dòng còn lại gồm hai số nguyên ~x~ và ~y~ ~(1 \le x,y \le n)~ là số hiệu hai trái ớt 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 ớt nhất và ít ớt nhất.

Scoring

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

Sample Input 3

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

Sample Output 3

2

Notes

• Ở ví dụ thứ nhất có ~3~ cách cắt để tạo thành một đùm có ~2~ trái ớt và hai đùm có một trái ớt. Do đó độ chênh lệch là ~2-1=1~;

• Ở ví dụ thứ ba, số lượng trái ớt trong các đùm lần lượt là ~4, 2, 3~ nên kết quả là ~4-2=2~.