Problem Description

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

Input Format

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

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

Output Format

The first line contains an integer $x$, the number of vertex-biconnected components.

The next $x$ lines: the first number is $a$, the number of nodes in this component, followed by $a$ numbers describing a vertex-biconnected component.

You may output the vertex-biconnected components in any order, and the nodes within each component in any order.

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

1
5 1 2 3 4 5

5 3
1 2
2 3
1 3

3
1 4
1 5
3 1 2 3

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

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

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

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

1 1
1 1

1
1 1

Hint

Explanation for Sample 4:

Nodes with the same color belong to the same component.

Friendly reminder: Please carefully consider isolated nodes and self-loops (Sample 5).

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

This problem is not strict on constant factors. Both the time limit and memory limit are set large, so any correct solution can pass.

Data Updates

• $2022/7/14$ Strengthened the testdata.
• $2022/11/26$ Added $10$ groups of smaller testdata ($1 \le n, m \le 10$) for easier debugging.
• $2022/12/31$ Reorganized the $subtask$ setup and added several groups of extreme testdata.
• $2023/1/1$ Found an issue in the testdata added yesterday, and it has been fixed.
• $2025/10/29$ Added an extra hack test.

Surprise: After getting AC, remember to place your mouse over the test points to see the feedback information. There is a surprise.

Translated by ChatGPT 5