Components of edge biconnectivity

In graph theory, a component of edge connectivity of a graph $(V,E)$ is defined as the largest subset of vertices $S\subset V$ such that for any two distinct vertices $\{u,v\}\subset S$, there exist at least two edge-disjoint paths between $u$ and $v$.

Given an undirected graph, your task is to determine its components of edge connectivity.

Input

The first line of the input contains two integers $n$ and $m$ — the number of vertices and edges in the graph, respectively $(n\le 20000,m\le 200000)$. The next $m$ lines each describe an edge with two integers $(b_j,e_j)$ — the vertices connected by the edge $(1\le b_j,e_j\le n)$.

Output

On the first line of the output, print the integer $k$ — the number of edge connectivity components in the graph. On the second line, print $n$ integers $a_1,a_2,\dots ,a_n$, each not exceeding $k$, where $a_i$ indicates the edge connectivity component to which the $i$-th vertex belongs.

Examples