Source: Library Checker
Statement
Given a directed graph with N vertices and M edges. i-th edge is (ai,bi). This graph may not be simple.
Please decompose this graph into SCCs and print them in topological order.
N 頂点 M 辺の有向グラフが与えられる。i 番目の辺は (ai,bi) である。このグラフは単純とは限らない。 このグラフを強連結成分分解し、トポロジカルソートして出力してください。
Constraint
- 1≤N≤500,000
- 1≤M≤500,000
- 0≤ai,bi<N
Input
- N M
- a0 b0
- a1 b1
- :
- aM−1 bM−1
Output
First line, print the number of SCCs K. Following K line, we print the information of SCC for each line as follows. l is the number of vertices of SCC, and vi is the vertex index.
K を強連結成分の行数として、1+K 行出力する。 最初の行には K を出力し、その後 K 行では以下のように出力する。l は強連結成分の頂点数であり、vi はその頂点番号である。
l v0 v1 ... vl−1
For each edge (ai,bi), the line that contains bi can not be earlier than the line that contains ai.
If there is a multiple solution, print any of them.
ここで、各辺 (ai,bi) について、bi が ai より __先の行__ に出現してはならない。
なお、正しい出力が複数存在する場合は、どれを出力しても構わない
Example
Input
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2
Output
4
1 5
2 4 1
1 2
2 3 0