Edge Biconnected Components

Given an undirected graph with n nodes and m edges, your task is to compute the number of edge biconnected components and output each component.

An edge biconnected component (or 2-edge-connected component) is defined as a maximal set of edges such that any two edges lie on a common simple cycle. Equivalently, after removing all bridges from the graph, the remaining edges in each connected part form an edge biconnected component. Note that if an edge is a bridge (i.e. its removal increases the number of connected components), then it forms a component by itself.

You are given a graph in which vertices are numbered from 1 to n. The graph is provided as a list of m edges. For each edge, the two endpoint vertices are given. Output first the number of edge biconnected components, and then for each component output the number of edges in the component followed by the list of the corresponding edge indices (according to their input order, starting from 1) in ascending order.

Note: If an edge is a bridge it constitutes a component consisting only of that edge.

Mathematical Formulation:

Let G(V,E) be an undirected graph. An edge e∈E is a bridge if \( \text{disc}(e)=\text{min}\{ \text{low}(u),\text{low}(v) \} < \text{disc}(e)\ \) does not hold (or formally, removal of e increases the number of connected components). The set of non-bridge edges contained in the same connected subgraph (when bridges are removed) forms an edge biconnected component.

inputFormat

The first line contains two integers n and m representing the number of nodes and edges respectively.

Then m lines follow, each containing two integers u and v indicating that there is an undirected edge between nodes u and v.

outputFormat

Output the number of edge biconnected components in the graph on the first line.

Then for each component, output a line starting with the number of edges in that component followed by the sorted list of edge indices (1-indexed as given in the input) that belong to that component.

sample

4 4
1 2
2 3
3 1
3 4

2
3 1 2 3
1 4