Centre for Gifted Education - Hanoi university of Technology

Định lý bốn màu cho rằng đối với bất kỳ mặt phẳng nào được chia thành các vùng phân biệt, chẳng hạn như bản đồ hành chính của một quốc gia, chỉ cần dùng tối đa bốn màu để phân biệt các vùng lân cận với nhau. Hai vùng được coi là lân cận nếu như chúng có chung nhau một đoạn đường biên, không tính chung nhau một điểm. Mỗi vùng như vậy phải liên tục, không có sự phân cách trong nội vùng như ở một số quốc gia như Mỹ, Azerbaijan hay Angola.

Tô màu đồ thị (graph coloring)

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 <= 100)

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