Nông dân John vừa đầu tư cho trang trại của mình một hệ thống đường ống dẫn nước. Vì trang trại của anh ta ở trên một ngọn núi cao nên việc đưa được nước đến từng chuồng bò là rất khó khăn. Hệ thống ống dẫn sẽ bơm nước từ một con sông nằm ở chân núi lên và chảy vào từng chuồng bò theo một mạng lưới. Hệ thống ống dẫn này gồm ~n~ chuồng bò được đánh số từ 1 tới ~n~ và ~n-1~ đường ống nối giữa hai chuồng bò với nhau. Biết rằng mỗi lần nước chảy từ chuồng ~u~ qua chuồng ~v~ thông qua ống dẫn trực tiếp giữa hai chuồng sẽ mất khoảng thời gian là 1 ngày. Hệ thống ống dẫn này đảm bảo cung cấp nước cho ~n~ chuồng bò. Ban đầu nước sẽ được đưa vào chuồng bò mang số hiệu 1.

Yêu cầu: Hãy tính toán xem mỗi chuồng bò sau bao nhiêu ngày thì bắt đầu có nước.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \le 10^5~) cho biết số lượng chuồng bò;
• ~n-1~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~u, v~ cho biết có đường ống dẫn nước trực tiếp giữa chuồng ~u~ và ~v~.

Kết quả

Ghi ra gồm ~n~ dòng, dòng thứ ~i~ cho biết thời gian chuồng bò thứ ~i~ nhận được nước.

Ví dụ

Water.inp

4
1 2
1 3
4 2

Water.out

0
1
1
2

Giải thích: Đầu tiên nước chảy vào chuồng 1, sau đó nước chảy từ chuồng 1 sang chuồng 2, 3; tiếp tục nước chảy từ chuồng 2 sang chuồng 4.

Giới hạn

• Có 20% số test ứng với 20% điểm của bài với ~1 \le n \le 10~;
• Có 20% số test ứng với 20% điểm của bài với ~10 < n \le 30000~.