Sau một buổi làm vườn mệt nhọc, Mr. Malnar quyết định tự thưởng cho mình bằng cách thưởng thức các bữa ăn trong ngày cùng với những quả ớt khô "siu kay" do chính tay ông trồng.

Ông có ~n~ quả ớt đang phơi trên giá và chúng được nối với nhau bởi ~n-1~ sợi dây. Thế nên, với hai quả ớt bất kì, chúng sẽ được nối với nhau bằng một dãy những sợi dây nào đó. Dễ hiểu hơn, những quả ớt sẽ hình thành một cấu trúc â .

Mr. Malnar sẽ dùng ớt trong cả ba bữa ăn hôm nay. Vì thế, ông sẽ cắt hai dây chỉ để chia ớt ra thành ba phần, một phần cho mỗi bữa.

Ông biết ăn cay nhiều là không tốt, nên ông muốn chia ớt ra sao cho đều nhất có thế. Vì thế ông sẽ chọn cách cắt dây sao cho: Chênh lệch lượng ớt giữa phần nhiều nhất với phần ít nhất là nhỏ nhất.

Nhiệm vụ của bạn là giúp Mr. Malnar tìm chênh lệch của cách cắt dây tốt nhất.

Input

Gồm nhiều dòng.

Dòng đầu tiên chứa số nguyên ~n~ , số lượng ớt trên giá. Những quả ớt được đánh số từ ~1~ đến ~n~ .

Mỗi dòng trong ~n-1~ dòng tiếp theo chứa hai số nguyên ~x~ và ~y~ ~(1 \le x,y \le n)~ - chỉ số của hai quả ớt được nối trực tiếp bởi một sợi chỉ.

Output

Gồm một dòng chứa một số nguyên dương là kết quả bài toán - Chênh lệch nhỏ nhất có thể.

Scoring

• Subtask 1: gồm 5 test với giới hạn ~3 \le n \le 200~ .
• Subtask 2: gồm 5 test với giới hạn ~3 \le n \le 2000~ .
• Subtask 3: gồm 10 test với giới hạn ~3 \le n \le 200000~ .

Sample 1

Input

4
1 2
2 3
3 4

Output

Sample 2

Input

6
1 2
1 3
3 4
3 5
5 6

Output

Sample 3

Input

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

Output

2