Problem8209--[yosupo] Graph - Biconnected Components

8209: [yosupo] Graph - Biconnected Components

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB  Special Judge

SubmitSolved: 2Submit Num: 3StatisticsShowOff!

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 but never has a self-loop.Decompose this graph into biconnected components and output their vertex sets.
A biconnected component is a maximal biconnected subgraph.

Input

$N$ $M$
$a _ 0$ $b _ 0$
$a _ 1$ $b _ 1$
:
$a _ {M-1}$ $b _ {M-1}$

Output

Print the number of biconnected components $K$ in the first line.Following $K$ lines, print as follows. $l$ is the number of vertices of biconnected components and $v _ i$ is an vertex index.
$l$ $v _ 0$ $v _ 1$ ... $v _ {l-1}$
If there is multiple solutions, print any of them.

Constraints

$1 \leq N \leq 5\times 10^5$
$0 \leq M \leq 5\times 10^5$
$0 \leq a _ i, b _ i \lt N$
$a _ i \neq b _ i$

Sample 1 Input 

4 5
0 3
0 1
3 0
2 1
2 3

Sample 1 Output 

1
4 0 1 2 3

Sample 2 Input 

10 12
0 6
0 8
1 2
1 6
2 6
3 6
3 9
4 9
4 7
5 6
5 9
6 8

Sample 2 Output 

5
3 0 6 8
3 1 2 6
4 3 5 6 9
2 4 7
2 4 9

Sample 3 Input 

5 3
0 1
1 0
0 1

Sample 3 Output 

4
2 0 1
1 2
1 3
1 4

HINT

相同题目：Yosupo.jp。

Source/Category

 
Submit