Vị quốc vương của đất nước Alpha có 3 chàng hoàng tử. Vì đã đến tuổi "gần đất xa trời", quốc vương muốn giao lại đất nước Alpha cho cả 3 người con quản lý. Đất nước Alpha có ~N~ thành phố và ~N~ − 1 con đường hai chiều nối giữa các thành phố. Đồng thời, xuất phát từ một thành phố bất kỳ, có thể đi đến ~N~ − 1 thành phố còn lại thông qua các con đường.

Điều khiến quốc vương đau đầu suốt mấy tháng nay là làm sao để chia đất nước cho 3 người con quản lý một cách công bằng nhất. Cụ thể, nhà vua muốn chia đất nước thành 3 vùng liên thông với nhau, mỗi vùng do một người con quản lý, sao cho chênh lệch giữa vùng nhỏ nhất và lớn nhất là nhỏ nhất có thể.

Kích thước của một vùng được tính bằng số lượng thành phố thuộc vùng đó. Bạn hãy giúp quốc vương tìm ra cách chia tối ưu nhất nhé.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ tương ứng với số lượng thành phố của vương quốc.
• ~N~ −1 dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u~ và ~v~ tương ứng với có con đường hai chiều nối giữa hai thành phố ~u~ và ~v~.

Kết quả

• In ra độ chênh lệch nhỏ nhất có thể đạt được với cách chia tối ưu.

Ví dụ

Sample Input

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

Sample Output

2

Giới hạn

• Subtask1(15%): 3≤~N~≤200.
• Subtask 2 (35%): 3 ≤ ~N~ ≤ 2000.
• Subtask 3 (60%): 3 ≤ ~N~ ≤ 200000.

Giải thích

Ở ví dụ trên, có thể chia đất nước thành 3 vùng (1, 2, 3, 4); (5, 6); (7, 8, 9), các thành phố trong từng vùng đều liên thông với nhau, chênh lệch giữa vùng lớn nhất và nhỏ nhất là 4 − 2 = 2. Đây cũng là cách chia tối ưu.

Nguồn: Free Contest