Triangle Trees

문제

A triangle tree is an undirected graph in which every cycle contains exactly three edges. Recall that a cycle is a sequence of at least $3$ distinct vertices $v_1,v_2,\dots ,v_k$ such that there is an edge between $v_i$ and $v_{i+1}$ for $i=1,\dots ,k-1$ and there is also an edge between $v_k$ and $v_1$.

A colouring of a graph is an assignment of colours to the vertices such that the two endpoints of each edge of the graph receive different colours. Given a triangle tree, your task is to find a colouring which uses the smallest possible number of colours.

Figure 1: Illustration of the second sample case. The number written just outside the vertex corresponds to the colour it receives corresponding to the output for that sample case.

입력

The first line of input contains two integers $N$ ($1\le N\le {10}^5$) and $M$ ($0\le M\le {10}^5$). The next $M$ lines each contain two integers $u$ and $v$ ($1\le u,v\le N$) indicating that the graph contains an edge between $u$ and $v$. It is guaranteed that $u\ne v$, all edges are unique, and that the graph is indeed a triangle tree.

출력

Output $N$ integers indicating the colours of vertices $1,2,\dots ,N$ in order. If you used $k$ colours, the integers should be from the set $\{1,2,\dots ,k\}$. If there are multiple valid colourings, you may output any one of them. Recall the goal is to output such a colouring using the fewest colours possible, i.e. minimize $k$.

예제 입력 1 복사

3 3
1 2
2 3
3 1

예제 입력 2 복사

7 8
1 2
1 7
2 7
3 4
3 7
4 7
5 7
6 7

예제 입력 3 복사

5 4
1 2
1 3
2 4
2 5

예제 출력 1 복사

2 3 1

예제 출력 2 복사

3 2 3 2 2 2 1

예제 출력 3 복사

1 2 2 1 1