You have read online that if a graph can be drawn on a plane such that the edges intersect only at their endpoints, then it can be colored with four colors such that the endpoints of each edge have distinct colors. Before implementing an algorithm for coloring such graphs with four colors, you decide to start with a simpler problem: designing an algorithm that colors them with six colors.

Input

The first line of the input contains two integers n and m.

The following m lines contain two integers v and u each, stating that there is an edge between vertices v and u.

Output

Output n integers such that the ith integer is between 1 and 6 and describes the color of the ith vertex.

Constraints

• 1 \le n, m \le 2 \cdot 10^5
• Each edge is unique.
• There is an undirected path between all pairs of vertices.
• The graph can be drawn on a plane without the edges intersecting.

Example

Input:

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

Output:

1 2 3 1 3