Graph condensation

Input

The graph is given as follows: the first line contains integers $n$ and $m$ (1 \leq n \leq 20000, 1 \leq m \leq 200000). Each of the next $m$ lines contains a description of an edge — two integers from $1$ to $n$, the start and end vertex of the edge.

Output

Output the total number of strongly connected components in the graph. On the next line, output $n$ integers — for each vertex, output the number of the strongly connected component it belongs to. Number the components so that for any edge, the component number of its starting vertex is less than or equal to the component number of its ending vertex.

Examples