8207: [yosupo] Graph - Two-Edge-Connected Components
[Creator : ]
Description
Given a undirected 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 two-edge-connected components.
This graph may not be simple.
Please decompose this graph into two-edge-connected components.
Input
$N\ M$
$a_0\ b_0$
$⋮$
$a_{M-1}\ a_{M-1}$
$a_0\ b_0$
$⋮$
$a_{M-1}\ a_{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.
$l\ v_0\ v_1\ \cdots\ v_{l−1}$
Following K lines, print as follows. l is the number of vertices of two-edge-connected components and $v_i$ is a vertex index.
$l\ v_0\ v_1\ \cdots\ v_{l−1}$
If there is multiple solutions, print any of them.
Sample 1 Input
4 5
0 2
0 1
3 0
2 1
2 3
Sample 1 Output
1
4 0 2 1 3
Sample 2 Input
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
Sample 2 Output
3
6 0 9 1 5 4 11
4 2 10 3 12
3 6 7 8
Sample 3 Input
2 2
0 1
1 0
Sample 3 Output
1
2 0 1