Problem11260--[yosupo] Graph - Connected Components of Complement Graph

11260: [yosupo] Graph - Connected Components of Complement Graph

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

SubmitSolved: 3Submit Num: 4StatisticsShowOff!

Description

You are given a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge is $(a_i,b_i)$. Decompose the complement graph of $G$ into connected components.

Input

$N$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{M-1}$ $b_{M-1}$

Output

Print the number of connected components $K$ in the first line. In the next $K$ lines, print as follows. $l$ is the number of vertices of a connected component and $v_i$ is a vertex index.
$l$ $v_0$ $v_1$ $...$ $v_{l−1}$
If there are multiple solutions, you may 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 < N$
- The given graph is simple

Sample 1 Input 

4 3
1 0
2 1
1 3

Sample 1 Output 

2
3 0 2 3
1 1

Sample 2 Input 

6 11
0 1
0 2
0 4
1 2
1 3
1 5
2 3
2 4
2 5
3 4
4 5

Sample 2 Output 

3
3 0 3 5
2 1 4
1 2

Sample 3 Input 

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

Sample 3 Output 

5
1 4
1 3
1 2
1 1
1 0

HINT

Yosupo.

Source/Category

 
Submit