Tý có đồ thị vô hướng gồm \(N\) đỉnh và \(M\) cạnh. Bạn cần tô màu các đỉnh sao cho hai đỉnh kề nhau không cùng màu và số màu sử dụng là tối thiểu có thể.

Hãy tìm cách tô màu với số màu nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa \(N\) và \(M\) (\(1 \le N \le 100\), \(0 \le M \le \frac{N(N-1)}{2}\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(u, v\) (\(1 \le u, v \le N\)) mô tả một cạnh.

Định dạng đầu ra

• Dòng đầu chứa số màu \(K\) đã sử dụng.
• Dòng thứ hai chứa \(N\) số nguyên, màu của các đỉnh \(1, 2, \ldots, N\) (màu đánh số từ \(1\)).

Ví dụ

Input:

4 4
1 2
1 3
2 4
3 4

Output:

2
1 2 2 1

Ràng buộc