Cho một cây gồm N nút, hãy tìm cách gán mỗi đỉnh một nhãn nguyên dương sao cho:

• Hai nút có cạnh nối được gán bởi hai nhãn khác nhau.
• Tổng giá trị các nhãn là nhỏ nhất.

Input

Dòng đầu tiên ghi N ( 1 ≤ N ≤ 10000).
N-1 dòng tiếp theo, mỗi dòng ghi hai nút là hai đầu mút của một cạnh thuộc cây.

Output

Dòng đầu tiên ghi S là tổng giá trị nhãn tìm được.
N dòng tiếp theo, dòng thứ i ghi nhãn gán cho đỉnh i trong phép gán tối ưu tìm được.

Example

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

Output
11
3
1
1
1
2
1
1
1