Problem Description

Given an undirected complete graph with $n$ nodes, delete $m$ edges from it. Find how many connected components the graph has.

Output the number of connected components, and output the details of each connected component.

Input Format

The first line of input contains two positive integers $n, m$, separated by a space, representing the number of nodes and the number of deleted edges.

The next $m$ lines each contain two positive integers $u_i, v_i$, separated by a space, indicating that the edge between $u_i$ and $v_i$ is deleted. It is guaranteed that the same edge will not be deleted twice.

Output Format

The first line of output contains an integer $x$, representing the number of connected components.

The next $x$ lines each describe one connected component. The first number $y$ indicates the number of nodes in this connected component, followed by $y$ numbers giving the node indices in order, with a space between adjacent integers. Output the connected components in increasing order of their smallest node; within each connected component, output the nodes in increasing order.

5 6
1 2
2 4
2 5
1 3
3 4
3 5

2
3 1 4 5
2 2 3

Hint

Constraints and Conventions for Test Cases

For $40\%$ of the test cases, $n \le 1000$.

For all test cases, $1 \le n, m \le 2 \times 10^5$, $m \le \dfrac{n(n-1)}{2}$, and $1 \le u_i, v_i \le n$.

Translated by ChatGPT 5