Ở đây, ta cần biết những định nghĩa sau:

• Một cây gồm ~n~ đỉnh là một đồ thị vô hướng, liên thông, không chu trình. Dễ dàng nhận thấy, một đồ thị như vậy luôn có chính xác ~n-1~ cạnh.
• Một cây có gốc tại ~i~ là một cây, trong đó nút ~i~ được coi là nút gốc, và không có nút nào ở phía trên (còn gọi là nút cha). Trong 2 nút liền kề: một nút sẽ là nút cha của nút còn lại, và tương ứng nút kia sẽ là nút con.
• Cây con tại đỉnh ~x~ của cây có gốc ban đầu là một cây chỉ gồm ~x~ và các đỉnh con cháu của nó, cùng với các cạnh nối các đỉnh đó.
• Đường kính của một cây là độ dài lớn nhất của đường đi giữa 2 đỉnh bất kỳ trên một cây.

Bạn được cung cấp 1 cây gồm ~n~ đỉnh, có gốc tại đỉnh ~1~. Gọi ~d_i~ là đường kính của cây con tại đỉnh ~i~ (~1 \le i \le n~).

Nhiệm vụ của bạn là tính tất cả các giá trị ~d_1, d_2, \ldots, d_n~.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 10^5~) là số đỉnh của cây.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~x~ và ~y~ (~1 \le x, y \le n~, ~x \ne y~); cho biết có cạnh nối 2 đỉnh ~x~ và ~y~ trên cây.
• Input đảm bảo dữ liệu nhập vào chắc chắn lập thành một cây, tức là có đủ tính chất của một cây như đã đề cập ở trên.

Output

In ra ~n~ số nguyên: ~d_1, d_2, \ldots, d_n$$~-- đường kính của các cây con tại đỉnh ~1, 2,\ldots, n~.

Sample

Input #1

4
1 2
1 3
1 4

Output #1

2 0 0 0

Input #2

2
1 2

Output #2

1 0

Input #3

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

Output #3

6 3 2 0 0 0 1 0 3

Problem source: CLB Lập Trình PTIT