Finding Blocks in an Undirected Graph

In your discrete mathematics course you learned about cut vertices and blocks (biconnected components) in undirected graphs. In this problem, you are given an undirected graph with \(n\) vertices and \(m\) edges. The vertices are numbered from 1 to \(n\). The graph may contain multiple edges (parallel edges) and self loops, and it is not guaranteed to be connected.

A block is defined as a maximal biconnected subgraph. Note that a vertex with no adjacent edges (an isolated vertex) does not form a block by itself. (A self loop is considered as an edge, so a vertex with a self loop does count as having an edge.)

Your task is to compute all the blocks of the graph. In the output, each block should be output in the following order:

1. For each block, sort the vertices in that block in increasing order.
2. Then, order the blocks by comparing their sorted vertex sequences in lexicographical order (i.e. compare the first vertex; if equal, compare the second, and so on).

Finally, output the total number of blocks followed by each block on a separate line. Each block line should list the vertex numbers separated by a single space.

Note: In this problem, isolated vertices (with no incident edge) are not counted as blocks.

inputFormat

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

Then \(m\) lines follow, each containing two integers \(u\) and \(v\) \((1 \leq u, v \leq n)\). Each line represents an undirected edge between vertices \(u\) and \(v\). Note that there might be multiple edges and self loops.

outputFormat

First, print an integer \(k\) on a line, representing the number of blocks in the graph.

Then, print \(k\) lines. Each line contains the vertices in one block separated by a single space. The vertices in each block must be sorted in increasing order, and the blocks must be output in lexicographical order based on their vertex sequences.

sample

3 3
1 2
2 3
3 1

1
1 2 3