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 two-edge-connected components.
N 頂点 M 辺の無向グラフが与えられる。i 番目の辺は (ai,bi) である。このグラフは単純とは限らない。 このグラフを二辺連結成分分解してください。
Constraint
- @1 \leq N \leq 2 \times 10^5
- @1 \leq M \leq 2 \times 10^5
- 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
Print the number of two-edge-connected components K in the first line. Following K lines, print as follows. l is the number of vertices of two-edge-connected components and v_i is a vertex index.
K を二辺連結成分の個数として、1 + K 行出力する。 最初の行には K を出力し、その後 K 行では以下のように出力する。l は二辺連結成分の頂点数であり、v_i はその頂点番号である。
- l v_0 v_1 ... v_{l-1}
If there is multiple solutions, print any of them.
正しい出力が複数存在する場合は、どれを出力しても構わない。
Examples
Input 1
4 5
0 2
0 1
3 0
2 1
2 3
Output 1
1
4 0 2 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
3
6 0 9 1 5 4 11
4 2 10 3 12
3 6 7 8
Input 3
2 2
0 1
1 0
Output 3
1
2 0 1