31293번 - Graph Coloring 스페셜 저지다국어

문제

You are given a bidirectional graph where the degree of each vertex is at most 5. Paint its vertices in 3 colors in such a way that each vertex $v$ has no more than one neighbor of the same color as $v$.

입력

On the first line, there are two integers $n$ and $m$: the number of vertices and the number of edges (1ドル \le n \le 100,000円$).

Each of next $m$ lines contains two integers $a$ and $b$: the numbers of vertices connected by an edge (1ドル \le a, b \le n$).

It is guaranteed that there are no loops or multiple edges in the graph, and the degree of each vertex is at most 5.

출력

It there is no valid coloring, print one number "-1" (without quotes). Otherwise, print $n$ integers $c_1,ドル $c_2,ドル $\ldots,ドル $c_n$: the colors of all vertices (1ドル \le c_i \le 3$). If there is more than one solution, print any one of them.

제한

힌트