Tặng quà

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 $2$ cành cây bất kì (hai cành khác nhau) để có được $3$ đùm ớt, mỗi đùm cho mỗi bữa. Mỗi đùm là một phần liên thông còn lại sau khi cắt, số trái ớt của đùm là số trái ớt trong phần đó.

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à đùm có ít ớt nhất là nhỏ nhất.

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

Dữ liệu vào

• 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 $2$ số nguyên $x$ và $y$ ($1\le x,y\le n$) là số hiệu $2$ trái ớt nối trực tiếp với nhau.

Dữ liệu đảm bảo các cành tạo thành một cây.

Dữ liệu ra

In ra độ chênh lệch tối thiểu giữa đùm có nhiều ớt nhất và đùm có ít ớt nhất.

Ràng buộc

• $3\le n\le 200000$;
• $1\le x,y\le n$.

Subtasks

• Subtask 1 ($25\%$ số điểm): $3\le n\le 200$;
• Subtask 2 ($25\%$ số điểm): $3\le n\le 2000$;
• Subtask 3 ($50\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ