Problem Description

For a graph with $n$ nodes and $m$ undirected edges, please output the number of edge biconnected components and list each edge biconnected component.

Input Format

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

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

The graph may not be a simple graph; it may contain duplicate edges and self-loops.

Output Format

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

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

You can output the edge 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 5 4 2 3

Sample Input #2

5 3
1 2
2 3
1 3

Sample Output #2

3
3 1 3 2
1 4
1 5

Sample Input #3

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

Sample Output #3

4
3 1 2 3
1 4
1 5
1 6

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
1 1
5 2 5 3 6 4
1 7

Notes

Sample 4 Explanation:

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

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

Data Updates

• $2022/7/14$ Enhanced data
• $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 the newly added data yesterday and have corrected them.

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

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

见题面 Input 部分

见题面 Output 部分