#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
class Graph {
public:
static const int NIL = -1;
Graph(const int _v = 0):
v(_v),
edges(vector< vector<int> >(_v, vector<int>())) {}
int V() const {
return v;
}
vector<int>::const_iterator EdgesBegin(const int x) const {
return edges[x].begin();
}
vector<int>::const_iterator EdgesEnd(const int x) const {
return edges[x].end();
}
void AddEdge(const int x, const int y) {
edges[x].push_back(y);
edges[y].push_back(x);
}
void GetBiconnectedComponents(vector< vector<int> > &components, vector<int> &criticalVertices, vector< pair<int, int> > &criticalEdges) const {
vector<int> level = vector<int>(v, -1), minLevel = vector<int>(v, -1);
for (int x = 0; x < v; ++x) {
if (level[x] == -1) {
level[x] = 0;
vector< pair<int, int> > stack;
DFS(x, NIL, stack, level, minLevel, components, criticalVertices, criticalEdges);
}
}
sort(criticalVertices.begin(), criticalVertices.end());
criticalVertices.erase(unique(criticalVertices.begin(), criticalVertices.end()), criticalVertices.end());
}
vector< vector<int> > GetBiconnectedComponents() const {
vector< vector<int> > components;
vector<int> criticalVertices;
vector< pair<int, int> > criticalEdges;
GetBiconnectedComponents(components, criticalVertices, criticalEdges);
return components;
}
private:
int v;
vector< vector<int> > edges;
vector<int> GetComponent(const pair<int, int> &edge, vector< pair<int, int> > &stack) const {
vector<int> component;
pair<int, int> topEdge;
do {
topEdge = stack.back();
stack.pop_back();
component.push_back(topEdge.first);
component.push_back(topEdge.second);
} while (topEdge != edge);
sort(component.begin(), component.end());
component.erase(unique(component.begin(), component.end()), component.end());
return component;
}
void DFS(const int x, const int father, vector< pair<int, int> > &stack, vector<int> &level, vector<int> &minLevel, vector< vector<int> > &components, vector<int> &criticalVertices, vector< pair<int, int> > &criticalEdges) const {
minLevel[x] = level[x];
for (vector<int>::const_iterator y = edges[x].begin(); y != edges[x].end(); ++y) {
if (level[*y] == -1) {
level[*y] = level[x] + 1;
stack.push_back(make_pair(x, *y));
DFS(*y, x, stack, level, minLevel, components, criticalVertices, criticalEdges);
if (minLevel[*y] > level[x])
criticalEdges.push_back(make_pair(x, *y));
if (minLevel[*y] >= level[x]) {
criticalVertices.push_back(x);
components.push_back(GetComponent(make_pair(x, *y), stack));
}
}
}
bool usedFather = false;
for (vector<int>::const_iterator y = edges[x].begin(); y != edges[x].end(); ++y) {
if (!usedFather && *y == father)
usedFather = true;
else
minLevel[x] = min(minLevel[x], minLevel[*y]);
}
}
};
Graph G;
vector< vector<int> > Components;
void Solve() {
Components = G.GetBiconnectedComponents();
}
void Read() {
ifstream cin("biconex.in");
int v, e;
cin >> v >> e;
G = Graph(v);
for (; e > 0; --e) {
int from, to;
cin >> from >> to;
G.AddEdge(--from, --to);
}
cin.close();
}
void Print() {
ofstream cout("biconex.out");
cout << int(Components.size()) << "\n";
for (int i = 0; i < int(Components.size()); ++i) {
for (vector<int>::const_iterator x = Components[i].begin(); x != Components[i].end(); ++x)
cout << *x + 1 << " ";
cout << "\n";
}
cout.close();
}
int main() {
Read();
Solve();
Print();
return 0;
}