You are given a graph with n vertices and m edges. Find a way to color the vertices of the graph with the least number of colors such that the endpoints of each edge have different colors.

As this problem is too hard to solve in general graphs, the graphs given as input will always be chordal. A chordal graph is a graph where each cycle with four or more vertices has a chord. A chord is an edge connecting two vertices of the cycle that are not adjacent in the cycle.

Input

The first line of the input contains integers n and m, the number of vertices and the number of edges. Next m lines each contain two vertices u_i and v_i connected by an edge.

Output

The first line of output should contain the number of colors needed. The second line should contain the colors of the vertices.

Constraints

• 1 \le n \le 5 \cdot 10^5
• 1 \le m \le 5 \cdot 10^5
• 1 \le u_i, v_i \le n, u_i \neq v_i

Examples

Input:

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

Output:

3
1 2 3 3

Input:

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

Output:

4
1 2 3 4