Problem J
A Coloring Problem

Your local skate park has $N$ skating pits, and there are $M$ benches that connecting pairs of pits. In other words, the skate park forms a graph in which the pits are represented as nodes and the benches as edges.

The skat(e)man would like you to color each pit such that if two pits are connected by a bench, they cannot have the same color. We call such a coloring a “valid coloring”.

Input

The input consists of a description of a single graph. The first line contains two integers $N$ and $M$ ($N = 100$, $m = 4000$), where $N$ is the number of nodes in the graph, and $M$ is the number of edges.

The following $M$ lines contains two integers each $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$, $u_i \neq v_i$), describing that there exist an edge between node $u_i$ and $v_i$.

Output

Output $N$ integers on a single line, the respective color of each of the nodes $c_1, c_2, \ldots , c_N$ in a valid coloring, where $c_i$ $(1 \leq c_i \leq 10^9)$ is the color of the $i$-th node.

Scoring

Your solution will be tested on 1 single input file, and you have access to the input file further down on this page. The amount of points you recieve depends on the number of different colors used.

Example

Consider the following case where $N = 5$ and $M = 6$:

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

A valid coloring is

1 2 3 1 2

which would look like (Figure 1):

Figure 1: The coloring 1 2 3 1 2 which uses 3 different colors, where red represents color 1, green represents color 2, and blue represents color 3.

An invalid coloring of the same graph is

1 1 3 1 2

which would look like (Figure 2):

Figure 2: The coloring 1 1 3 1 2 which uses 3 different colors, where red represents color 1, green represents color 2, and blue represents color 3.

100 4000
13 88
97 81
98 46
89 77
17 58
91 7
82 38
55 84
...

[some valid coloring here]