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\)

Dữ liệu vào

• Dòng đầu tiên ghi \(N\) \((1 \le N \le 2 \times 10^5)\)
• \(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.

Dữ liệu ra

• 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.

Input 1

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

Output 1

11
2
1
1
1
3
1
1
1