QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓
[+6]

# 906. 强连通分量

Statistics

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

  • 1N500,000
  • 1M500,000
  • 0ai,bi<N

Input

  • N M
  • a0 b0
  • a1 b1
  • :
  • aM1 bM1

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 ... vl1

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) について、biai より __先の行__ に出現してはならない。

なお、正しい出力が複数存在する場合は、どれを出力しても構わない

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