Cho mạng lưới đường đi dạng một cái cây (gồm ~N~ nút, được đánh số từ 1 tới ~N~). Việt là một runner chạy việt dã chạy ~N-1~ chặng. Mỗi chặng thứ ~i~ xuất phát từ đỉnh ~i~ và kết thúc ở đỉnh ~i + 1~. Được biết lộ trình của Việt là tối ưu (ngắn nhất). Ban tổ chức muốn với mỗi lần Việt chạy qua một đỉnh ~i~ (tính cả điểm bắt đầu/kết thúc) cần có một chai nước tiếp tế.

Yêu cầu: Tính số chai nước tại mỗi nút.

Input

• Dòng đầu tiên chứa 1 số nguyên ~N~ là số lượng nút (~1 \le N \le 4 \times 10^5~).
• Mỗi dòng trong số ~N-1~ dòng tiếp theo, chứa hai số nguyên ~u~ và ~v~ cách nhau bởi dấu cách (~1 \le u, v \le N, u \ne v~) là cạnh trên cây.

Output

• Gồm ~N~ dòng. Ở dòng thứ ~i~ là số chai nước cần phải đặt tại nút ~i~.

Sample Input 1

5
1 2
2 5
2 4
5 3

Sample Output 1

1
4
2
2
3

Sample Input 2

10
1 3
1 5 
5 2 
5 9 
9 7 
9 10 
6 2 
4 2 
8 4

Sample Output 2

3
8
2
4
8
2
2
2
4
1