English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.
The problem statement has been automatically translated from Russian. If the statement is not clear, or you have any comments about it, please contact me. Anyway, I hope that someday I will fix the translation manually.

Graph condensation

You are given a directed graph with $N$ vertices and $M$ edges ($1\le N\le 20,000$, $1\le M\le 200,000$). Find the components of the strong connectivity of a given graph and topologically sort its condensation.

Input data

The graph is specified in the input file as follows: the first line contains the numbers $N$ and $M$. Each of the following $M$ lines contains a description of the edge — two integers from the range from $1$ to $N$ — the numbers of the beginning and end of the edge.

Output data

On the first line, print the number $K$ — the number of components of strong connectivity in a given graph. On the next line, print $N$ numbers — for each vertex, print the number of the component of strong connectivity to which this vertex belongs. The components of strong connectivity must be numbered in such a way that for any edge the number of the component of strong connectivity of its beginning does not exceed the number of the component of strong connectivity of its end.

Examples
Input data
10 19
1 4
7 8
5 10
8 9
9 6
2 6
6 2
3 8
9 2
7 2
9 7
4 5
3 6
7 3
6 7
10 8
10 1
2 9
2 7
Output data
2
1 2 2 1 1 2 2 2 2 1

This problem on informatics

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)