Giải bài trực tuyến

Cho đơn đồ thị vô hướng G = (E, V) có n đỉnh, m cạnh. Hãy tìm cách tô màu các đỉnh của đồ thị mỗi đỉnh 1 màu sao cho không có 2 đỉnh nào kề cạnh có cùng màu và số màu sử dụng là ít nhất.
Input
Dòng 1: Gồm 2 số n, m. (1 <= n <= 1000)
M dòng tiếp theo: Mỗi dòng gồm 2 số i, j mô tả 1 cạnh của đồ thị.
Output
Dòng 1: Ghi k là số màu ít nhất cần sử dụng.
n dòng tiếp theo: Dòng thứ i ghi màu của đỉnh i sau khi đã được tô.
Example
Input:
7 8
1 7
2 3
2 5
1 4
4 7
3 6
6 7
5 7

Output:
3
1
1
2
3
3
1
2