Background

For an undirected graph $G = (V, E)$.

• We say two vertices $u, v ~ (u, v \in V, u \neq v)$ are three-edge-connected if and only if there exist three paths from $u$ to $v$ that do not share any common edges.
• We say a vertex set $U ~ (U \subseteq V)$ is a three-edge-connected component if and only if for any two vertices $u', v' ~ (u', v' \in U, u' \neq v')$, they are three-edge-connected.
• We say a three-edge-connected component $S$ is a maximal three-edge-connected component if and only if there does not exist a vertex $u \not \in S$ with $u \in V$ such that $S \cup \{u\}$ is also a three-edge-connected component.

Problem 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