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.
• Nhãn của mỗi đỉnh không vượt quá ~N~.

Input

• Dòng đầu tiên ghi ~N~ ~(1 \leq N \leq 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.

Sample Input

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

Sample Output

11
2
1
1
1
3
1
1
1