Một đợt hạn hán kéo dài đã khiến \(N\) đồng cỏ của Farmer John không còn chút cỏ nào. Tuy nhiên, mùa mưa sắp đến và đã tới lúc "phủ xanh trở lại".

Trong nhà kho, Farmer John có bốn thùng, mỗi thùng chứa một loại hạt giống cỏ khác nhau. Ông muốn gieo một trong các loại hạt giống này trên mỗi đồng cỏ. Là một người chăn bò sữa, Farmer John muốn bảo đảm mỗi con bò của mình có chế độ ăn đa dạng. Mỗi con trong số \(M\) con bò có hai đồng cỏ yêu thích, và ông muốn bảo đảm hai đồng cỏ ấy được trồng các loại cỏ khác nhau để mỗi con bò có thể lựa chọn giữa hai loại cỏ. Farmer John biết rằng không có đồng cỏ nào là nơi yêu thích của nhiều hơn \(3\) con bò.

Hãy giúp Farmer John chọn một loại cỏ cho mỗi đồng cỏ sao cho nhu cầu dinh dưỡng của tất cả các con bò đều được đáp ứng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 100\)) và \(M\) (\(1 \leq M \leq 150\)). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên trong phạm vi \(1 \ldots N\), mô tả cặp đồng cỏ yêu thích của một con bò của Farmer John.

Dữ liệu ra

In ra một số gồm \(N\) chữ số, trong đó mỗi chữ số nằm trong phạm vi \(1 \ldots 4\) và mô tả loại cỏ cần trồng trên từng đồng cỏ. Chữ số đầu tiên tương ứng với loại cỏ của đồng cỏ \(1\), chữ số thứ hai tương ứng với đồng cỏ \(2\), và cứ tiếp tục như vậy. Nếu có nhiều phương án hợp lệ, chỉ in số gồm \(N\) chữ số nhỏ nhất trong số đó.

Ví dụ

5 6
4 1
4 2
4 3
2 5
1 2
1 5

12133

Nguồn

USACO 2019 February Contest, Bronze — The Great Revegetation

Tác giả: Dhruv Rohatgi.