Farmer John và các nông dân khác đã làm việc không ngừng để kiểm soát sự lây lan của căn bệnh COWVID-19 nguy hiểm trên các trang trại.

Họ cùng quản lý \(N\) trang trại (\(1\le N\le 10^5\)), được đánh số \(1\ldots N\). Các trang trại được nối bởi \(N-1\) con đường sao cho có thể đi từ trang trại \(1\) đến bất kỳ trang trại nào qua một dãy đường.

Không may, một con bò ở trang trại \(1\) vừa có kết quả dương tính với COWVID-19. Chưa có con bò nào khác tại trang trại đó hoặc các trang trại khác mắc bệnh. Tuy nhiên, vì biết bệnh dễ lây, Farmer John dự đoán đúng một trong hai sự kiện sau sẽ xảy ra trong mỗi ngày kế tiếp:

1. Tại một trang trại duy nhất, một sự kiện "siêu lây nhiễm" làm số bò mắc COWVID-19 ở trang trại đó tăng gấp đôi.
2. Một con bò mắc COWVID-19 đi theo một con đường từ trang trại hiện tại sang một trang trại kề.

Farmer John lo lắng về tốc độ lây lan của dịch bệnh. Hãy xác định số ngày ít nhất có thể để mỗi trang trại đều có ít nhất một con bò mắc bệnh.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một con đường giữa hai trang trại \(a\) và \(b\). Cả \(a\) và \(b\) đều thuộc đoạn \(1\ldots N\).

Dữ liệu ra

In số ngày ít nhất để dịch bệnh có thể lan tới mọi trang trại.

Phân nhóm

• Trong các test 1-4, mọi trang trại, ngoại trừ chính trang trại \(1\), đều nối trực tiếp với trang trại \(1\).
• Trong các test 5-7, mỗi trang trại \(2\ldots N\) kề với nhiều nhất hai con đường.
• Trong các test 8-15, không có ràng buộc bổ sung.

Ví dụ

4
1 2
1 3
1 4

5

Nguồn

USACO 2020 December Contest, Silver - Cowntagion: https://usaco.org/index.php?page=viewproblem2&cpid=1062

Tác giả: Dhruv Rohatgi.