Problem Description

Given an undirected graph with $n$ vertices and $m$ edges, output the number of its edge biconnected components, and output each edge 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.

The graph is not guaranteed to be a simple graph. There may be multiple edges and self-loops in the graph.

Output Format

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

The next $x$ lines: in each line, the first number is $a$, the number of vertices in this component, followed by $a$ numbers describing an edge biconnected component.

You may output the edge biconnected components and the vertices 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 5 4 2 3

5 3
1 2
2 3
1 3

3
3 1 3 2
1 4
1 5

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

4
3 1 2 3
1 4
1 5
1 6

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

3
1 1
5 2 5 3 6 4
1 7

Hint

Explanation for Sample 4:

Points with the same color belong to the same connected component.

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

Data Updates

• $2022/7/14$ testdata strengthened.
• $2022/11/26$ added $10$ new smaller test groups ($1 \le n, m \le 10$) to make debugging easier.
• $2022/12/31$ reorganized the $subtask$ setup and added several groups of extreme testdata.
• $2023/1/1$ found issues in the newly added testdata from yesterday, and fixed them.

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

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