Cắt ớt

Sau một buổi sáng làm vườn mệt mỏi, ông Malnar quyết định tự thưởng cho mình những quả ớt khô do chính tay ông trồng.

Ông có \(n\) quả ớt, được nối với nhau bằng \(n-1\) sợi dây, sao cho giữa mọi cặp quả ớt đều tồn tại đúng một đường đi. Nói cách khác, các quả ớt tạo thành một cây.

Hôm nay ông Malnar sẽ ăn trưa ba lần. Để chuẩn bị, ông sẽ cắt đúng hai sợi dây, tách cây thành ba thành phần rời nhau --- mỗi thành phần dành cho một bữa trưa.

Ông muốn tránh việc một bữa trưa quá cay hơn các bữa còn lại. Do đó, ông sẽ chọn hai vị trí cắt sao cho sự chênh lệch giữa kích thước lớn nhất và kích thước nhỏ nhất trong ba thành phần là nhỏ nhất có thể.

\InputFile

Dòng đầu tiên chứa số nguyên \(n\) (\(3 \le n \le 200\,000\)) --- số lượng quả ớt.

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\)), biểu diễn rằng giữa quả ớt \(x\) và \(y\) có một sợi dây nối trực tiếp.

\OutputFile

In ra một số nguyên --- khoảng chênh lệch nhỏ nhất giữa kích thước lớn nhất và kích thước nhỏ nhất của ba thành phần sau khi cắt hai sợi dây.

\Scoring

• Subtask 1 (15 điểm): \(3 \le n \le 200\).
• Subtask 2 (35 điểm): \(3 \le n \le 2000\).
• Subtask 3 (50 điểm): \(3 \le n \le 200000\).

Example

4
1 2
2 3
3 4

1

6
1 2
1 3
3 4
3 5
5 6

0

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

2