Hệ thống điện

Hệ thống điện quốc gia do tập đoàn Điện lực Việt Nam EVN quản lý là một mạng lưới gồm \(n\) trạm biến áp, được đánh số từ \(1\) đến \(n\). Giữa các trạm có \(n-1\) đường dây truyền tải, sao cho giữa hai trạm bất kỳ luôn tồn tại một dãy các đường dây nối chúng. Nói cách khác, hệ thống này tạo thành một cây có \(n\) đỉnh.

Để thực hiện công tác bảo trì định kỳ, Trung tâm điều độ lưới điện Quốc gia A0 phải ngắt tạm thời hai đường dây truyền tải giữa hai cặp trạm biến áp, nhằm chia mạng lưới thành ba cụm trạm biến áp độc lập. Mỗi cụm sẽ được bảo trì riêng biệt.

Vì yêu cầu kỹ thuật cân bằng tải của hệ thống, việc phân chia cần có sự cân bằng số trạm biến áp trong các cụm. Do đó các kỹ sư của A0 muốn lựa chọn hai đường dây nối giữa hai cặp trạm biến áp nào đó để ngắt sao cho độ chênh lệch giữa cụm có nhiều trạm nhất và cụm có ít trạm nhất là nhỏ nhất có thể.

Yêu cầu: Hãy xác định độ chênh lệch nhỏ nhất giữa cụm có nhiều trạm nhất và cụm có ít trạm nhất mà các kỹ sư có thể đạt được.

Input

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\), số lượng trạm biến áp cần chia (\(3 \le n \le 2 \cdot 10^5\)).

• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\)), thể hiện có một đường dây nối trực tiếp giữa trạm \(u\) và trạm \(v\).

Ràng buộc:

• Có \(25\%\) số test của bài thỏa mãn \(1 \le n \le 200\).

• Có \(25\%\) số test của bài thỏa mãn \(1 \le n \le 2000\).

• Có \(50\%\) số test còn lại không có ràng buộc gì thêm.

Output

In ra một số nguyên duy nhất là độ chênh lệch nhỏ nhất có thể giữa cụm có nhiều trạm nhất và cụm có ít trạm nhất sau khi ngắt hai đường dây.

Example 1

Input:

5
1 2
2 3
3 4
4 5

Output:

1

Example 2

Input:

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

Output:

2

Note

Ví dụ 1: ngắt hai đường dây \((1,2)\) và \((3,4)\) được các cụm có \(1\), \(2\), \(2\) trạm; chênh lệch là \(1\).

Ví dụ 2: ngắt hai đường dây \((3,5)\) và \((5,7)\) được các cụm có \(4\), \(2\), \(2\) trạm; chênh lệch là \(2\).