QOJ.ac

QOJ

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

# 1000. 边三连通分量

Statistics

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

  • 1N2×105
  • 1M2×105
  • 0ai,bi<N

Input

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

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

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