Source: Library Checker
Statement
Given a directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$. This graph may not be simple.
Please decompose this graph into SCCs and print them in topological order.
$N$ 頂点 $M$ 辺の有向グラフが与えられる。$i$ 番目の辺は $(a_i, b_i)$ である。このグラフは単純とは限らない。 このグラフを強連結成分分解し、トポロジカルソートして出力してください。
Constraint
- $1 \leq N \leq 500,000$
- $1 \leq M \leq 500,000$
- $0 \leq a_i, b_i < N$
Input
- $N$ $M$
- $a_0$ $b_0$
- $a_1$ $b_1$
- :
- $a_{M - 1}$ $b_{M - 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 $v_i$ is the vertex index.
$K$ を強連結成分の行数として、$1 + K$ 行出力する。 最初の行には $K$ を出力し、その後 $K$ 行では以下のように出力する。$l$ は強連結成分の頂点数であり、$v_i$ はその頂点番号である。
$l$ $v_0$ $v_1$ ... $v_{l-1}$
For each edge $(a_i, b_i)$, the line that contains $b_i$ can not be earlier than the line that contains $a_i$.
If there is a multiple solution, print any of them.
ここで、各辺 $(a_i, b_i)$ について、$b_i$ が $a_i$ より __先の行__ に出現してはならない。
なお、正しい出力が複数存在する場合は、どれを出力しても構わない
Example
Input
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2Output
4
1 5
2 4 1
1 2
2 3 0