Module: Strongly Connected Components and Graph Condensation

Problem

1
/1

Search for strongly connected components

Problem

You are given a directed graph with N vertices and M edges (1<=N<=20000, 1<=M<=200000). Find the strongly connected components of the given graph and topologically sort its condensation.

Input

The graph is given in the input file as follows: the first line contains the numbers N and M. Each of the next M lines contains a description of the edge — two integers from 1 to N — edge start and end numbers.

Output

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