Lây lan dịch bệnh

Cây $N$ trang trại. Dịch bệnh bắt đầu ở trang trại 1 (1 bò bệnh). Mỗi ngày, chọn 1 trang trại và làm 1 trong 2 việc: nhân đôi số bò bệnh, hoặc gửi 1 bò bệnh sang trang trại liền kề. Tìm số ngày tối thiểu để mọi trang trại có ít nhất 1 bò bệnh.

Dữ liệu vào

• Dòng đầu: $N$.
• $N-1$ dòng tiếp: cạnh cây.

Dữ liệu ra

Số ngày tối thiểu.

Ràng buộc

• $1\le N\le {10}^5$

Ví dụ