Source: Library Checker
Statement
Given a undirected graph with N vertices and M edges. i-th edge is (ai,bi). This graph may not be simple. Please decompose this graph into three-edge-connected components.
N 頂点 M 辺の無向グラフが与えられる。i 番目の辺は (ai,bi) である。このグラフは単純とは限らない。 このグラフを三辺連結成分分解してください。
Constraint
- 1≤N≤2×105
- 1≤M≤2×105
- 0≤ai,bi<N
Input
- N M
- a0 b0
- a1 b1
- :
- aM−1 bM−1
Output
Print the number of three-edge-connected components K in the first line. Following K lines, print as follows. l is the number of vertices of three-edge-connected components and vi is a vertex index.
K を三辺連結成分の個数として、1+K 行出力する。 最初の行には K を出力し、その後 K 行では以下のように出力する。l は三辺連結成分の頂点数であり、vi はその頂点番号である。
- l v0 v1 ... vl−1
If there is multiple solutions, print any of them.
正しい出力が複数存在する場合は、どれを出力しても構わない。
Example
Input 1
4 5
0 2
0 1
3 0
2 1
2 3
Output 1
3
2 0 2
1 1
1 3
Input 2
13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11
Output 2
6
1 0
3 1 9 5
4 2 12 3 10
2 4 11
1 6
2 7 8