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

Input

5 3
1 2
2 3
4 5

Output

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

Input

6 2
2 4
3 6

Output

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~.