Problem Description

Given an undirected graph with $n$ nodes and $m$ edges, output the number of biconnected components and list each biconnected component.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two integers $u$ and $v$, representing an undirected edge.

Output Format

The first line contains an integer $x$ representing the number of biconnected components.

The next $x$ lines each start with an integer $a$ representing the number of nodes in that component, followed by $a$ integers describing the nodes in that biconnected component.

You can output the biconnected components and the nodes within them in any order.

Sample Input and Output

Sample Input #1

5 8
1 3
2 4
4 3
1 2
4 5
5 1
2 4
1 1

Sample Output #1

1
5 1 2 3 4 5

Sample Input #2

5 3
1 2
2 3
1 3

Sample Output #2

3
1 4
1 5
3 1 2 3

Sample Input #3

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

Sample Output #3

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

Sample Input #4

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

Sample Output #4

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

Sample Input #5

1 1
1 1

Sample Output #5

1
1 1

Notes

Sample 4 Explanation:

Nodes of the same color belong to the same component.

Reminder: Please consider isolated nodes and self-loops (Sample 5).

Data Range:
For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $1 \le m \le 2 \times 10^6$.

This problem does not require optimization for speed. The time and space limits have been increased, and correct solutions will pass.

Data Updates

• $2022/7/14$ Data strengthened
• $2022/11/26$ Added 10 smaller datasets ($1 \le n, m \le 10$) for easier debugging.
• $2022/12/31$ Reorganized subtasks and added several extreme datasets.
• $2023/1/1$ Discovered issues with newly added data yesterday and have corrected them.

Surprise: After AC, remember to hover over the test points to see feedback messages, there's a surprise!

见题面 Input 部分

见题面 Output 部分