Maximal Edge 3-Connected Components

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

A subgraph \(H\) of \(G\) is called edge 3-connected if for any two distinct vertices \(u,v \in H\), there exist at least three edge-disjoint paths connecting \(u\) and \(v\). Equivalently, the edge connectivity of \(H\) is at least 3, i.e. the minimum number of edges whose removal disconnects \(H\) is at least 3.

The maximal edge 3-connected components are the maximal subsets of vertices induced in \(G\) such that the induced subgraph is edge 3-connected. Note that if a vertex does not belong to any nontrivial edge 3-connected subgraph, output it as a component of size 1.

Note: It is guaranteed that the input graph has small size so that a pairwise maximum flow computation is feasible.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 100)\), representing the number of vertices and edges respectively.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) \((1 \leq u, v \leq n, u \neq v)\) which denotes an undirected edge connecting vertices \(u\) and \(v\). There are no multiple edges.

outputFormat

On the first line, output an integer \(k\) representing the number of maximal edge 3-connected components.

Then, for each component, output a line beginning with an integer \(s\) (the number of vertices in the component) followed by \(s\) integers representing the vertices in that component in increasing order. The components can be output in any order.

sample

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

1
4 1 2 3 4