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ì để được \(3\) đùm ớt, mỗi đùm cho một bữa.

Yêu cầu: Phát muốn cắt sao cho độ chênh lệch giữa đùm có nhiều ớt nhất và ít nhất là nhỏ nhất. Bạn phải giúp anh ấy tìm độ chênh lệch đó.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(3 \le n \le 200\);
• Subtask \(2\) (\(50\%\) số điểm): \(3 \le n \le 2000\);
• Subtask \(3\) (\(100\%\) số điểm): \(3 \le n \le 200000\).

Input

Dữ liệu vào từ file CHILLIS.INP:

• Dòng đầu chứa số nguyên \(n\) là số lượng ớt. Các trái ớt được đánh số từ \(1 \rightarrow n\).
• Mỗi dòng trong \(n-1\) dòng còn lại gồm hai số nguyên \(x\) và \(y\) \(\left( 1 \le x, y \le n \right)\) số hiệu của hai trái ớt nối trực tiếp với nhau.

Output

Kết quả ghi vào file CHILLIS.OUT độ chênh lệch tối thiểu giữa đám có nhiều ớt nhất và ít ớt nhất.

Example