Connected Components

You are given an undirected graph with $n$ vertices numbered from $1$ to $n$.

Find all connected components of the graph. Components are numbered in the order they are first discovered by scanning vertices from $1$ to $n$. When an unvisited vertex is found, it starts the next component, and every vertex reachable from it receives that component number.

Input

The first line contains two integers $n$ and $m$, the number of vertices and edges.

The next $m$ lines each contain two integers $a$ and $b$, meaning there is an undirected edge between vertices $a$ and $b$.

Output

Print one integer $k$, the number of connected components.

Then print $n$ integers: the component label of each vertex from $1$ to $n$.

Constraints

• $1 \le n \le 200000$
• $0 \le m \le 300000$
• $1 \le a, b \le n$

Example 1

5 3
1 2
2 3
4 5

2
1 1 1 2 2

Explanation

Vertices $1, 2, 3$ form the first component, and vertices $4, 5$ form the second component.

Example 2

6 2
2 4
3 6

4
1 2 3 2 4 3

Explanation

Vertex $1$ starts component $1$. Vertices $2$ and $4$ form component $2$. Vertices $3$ and $6$ form component $3$. Vertex $5$ starts component $4$.