Description

Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, where $V = \{1, 2, \ldots, n\}$, find all of its maximal three-edge-connected components.

Input Format

The first line contains two integers $n, m$, representing the number of vertices and the number of edges.

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

Output Format

The first line outputs an integer $s$, representing the number of maximal three-edge-connected components.

Then output $s$ lines. Each line contains several integers, representing all vertices in one maximal three-edge-connected component.

For each maximal three-edge-connected component, output its vertices in increasing order of their labels. For all maximal three-edge-connected components, output them in increasing order of the smallest vertex label in each set.

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

3
1 3
2
4

17 29
1 2
1 10
1 10
2 3
2 8
3 4
3 5
4 6
4 6
5 6
5 6
5 7
7 8
7 11
7 12
7 17
7 17
8 9
9 10
11 12
11 17
12 13
12 16
13 14
13 15
13 16
14 15
14 16
15 16

7
1 10
2 8
3 4 5 6
7 11 17
9
12
13 14 15 16

Hint

Explanation for Sample 1

As shown in the figure, there are three paths from $1$ to $3$: $(1, 2, 3)$, $(1, 3)$, and $(1, 4, 3)$. They do not share any edges with each other. Therefore, $1$ and $3$ are in the same three-edge-connected component.

Since vertices $2$ and $4$ both have degree only $2$, it is impossible for them to have three edge-disjoint paths to other vertices, so each of them forms a three-edge-connected component by itself.

Constraints

• For $30\%$ of the testdata, $n \le 100$, $m \le 200$.
• For $50\%$ of the testdata, $n \le 1000$, $m \le 2000$.
• For $80\%$ of the testdata, $n \le 10 ^ 5$, $m \le 2 \times 10 ^ 5$.
• For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10 ^ 5$, $1 \le u, v \le n$. Multiple edges and self-loops may exist.

Source

This problem is adapted from Three-Edge-Connected Components。

Translated by ChatGPT 5