Những xưởng bia nhỏ hoàn toàn tự động được lắp đặt trong các khu mỏ bỏ hoang của người lùn ở Moravia thực sự là minh chứng cho sự khéo léo và tài nghệ kỹ thuật của họ! Tiếc thay, đôi khi động đất làm rung chuyển các khu mỏ, khiến các ống dẫn và phễu bị lệch, làm thứ chất lỏng quý giá tràn xuống sàn. Với cương vị Người bảo hộ tối cao về an toàn xưởng bia, bạn có trách nhiệm tắt máy móc trong mọi gian hầm khi xảy ra động đất.

Việc đi qua các đường hầm mất thời gian, nên bạn chắc chắn sẽ đến muộn ở nhiều máy. Điều này không thể tránh khỏi, nhưng bạn muốn giảm thiểu tổng lượng chất lỏng bị tràn.

Khu mỏ của người lùn gồm \(n\) gian hầm được nối bởi \(n-1\) đường hầm. Toàn bộ hệ thống liên thông, nghĩa là có thể đi từ bất kỳ gian hầm nào đến mọi gian hầm khác. Đi qua một đường hầm mất \(1\) đơn vị thời gian. Việc tắt máy móc và di chuyển bên trong một gian hầm không mất thời gian. Tại mỗi gian hầm, nếu tắt máy móc ở thời điểm \(t\) kể từ khi động đất xảy ra thì có \(t\) lít chất lỏng bị tràn.

Chỉ có đúng một trận động đất, tác động đồng thời đến tất cả các gian hầm, và bạn không được tắt bất kỳ máy nào trước khi động đất xảy ra. Bạn có thể bắt đầu ở bất kỳ gian hầm nào.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số gian hầm. Các gian hầm được đánh số từ \(1\) đến \(n\).

\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) cách nhau bằng dấu cách, thỏa mãn \(1\le u<v\le n\), cho biết có một đường hầm nối gian \(u\) với gian \(v\).

Dữ liệu ra

In một số nguyên duy nhất: lượng chất lỏng bị tràn ít nhất, tính bằng lít.

Ràng buộc

• \(1\le n\le 10^5\).
• Hệ thống gồm \(n\) gian hầm và \(n-1\) đường hầm, và liên thông.

Phân nhóm

Các bộ kiểm thử được chia thành các nhóm, mỗi nhóm có một số điểm. Để nhận được điểm của một nhóm, chương trình phải giải đúng tất cả các bộ kiểm thử trong nhóm đó. Điểm cuối cùng là điểm cao nhất của một lần nộp bài.

1. \(18\) điểm: không có gian hầm nào nối với hơn hai đường hầm.
2. \(19\) điểm: có nhiều nhất một gian hầm nối với hơn hai đường hầm.
3. \(20\) điểm: \(n\le 10\).
4. \(21\) điểm: \(n\le 1000\).
5. \(22\) điểm: không có ràng buộc bổ sung.

Ví dụ

3
1 2
2 3

3

4
1 2
1 3
1 4

7

1

0