Cho cây \(n\) đỉnh, tìm cách tô các đỉnh bằng các màu từ \(1\) đến \(n\) thỏa mãn:

• Các đỉnh được tô cùng một màu tạo thành một đường đi.
• Gọi màu tô của đỉnh \(u\) là \(c_u\), thì dãy \(c_1, c_2, \ldots, c_n\) có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) mô tả các cạnh của cây.

Output

• In ra \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) mô tả cách tô màu cây.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 5 \times 10^2\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 5 \times 10^3\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

1 1 1 2 3 3 2 2