Bạn được cho ~n+1~ đỉnh và ~n-1~ cạnh, ~n~ đỉnh đầu tiên tạo thành một cây và đỉnh ~n+1~ không được nối với bất kì đỉnh nào khác. Với mỗi đỉnh từ ~1~ đến ~n~, hãy trả lời câu hỏi sau:

Nếu một cạnh nối giữa đỉnh ~i~ và đỉnh ~n+1~ được thêm vào, đường kính của cây được tạo thành là bao nhiêu? (Nhận thấy tất cả ~n+1~ đỉnh sẽ tạo thành một cây sau khi thêm cạnh này vào)

Input

Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \le n \le 3 \times 10^5)~ là số đỉnh trong cây ban đầu.

~n-1~ dòng tiếp theo mô tả các cạnh của cây. Dòng thứ ~i~ chứa ~2~ số nguyên ~u_i~, ~v_i~ ~(1 \le u_i, v_i \le n,\ u_i \neq v_i)~ thể hiện có cạnh nối giữa đỉnh ~u_i~ và ~v_i~. Dữ liệu đảm bảo các cạnh tạo thành một cây.

Output

In ra ~n~ dòng, mỗi dòng chứa đường kính của cây được tạo thành sau khi thêm một cạnh nối giữa đỉnh ~i~ và đỉnh ~n+1~.

Sample 1

Input

1

Output

1

Sample 2

Input

3
3 2
2 1

Output

3
2
3

Sample 3

Input

5
4 2
1 4
5 4
3 4

Output

3
3
3
2
3