#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <stdlib.h>
#include <limits.h>
#include <vector>
struct gList
{
int nod, cost;
struct gList *next;
};
struct Graph
{
gList **adj;
int n;
};
struct Edge
{
int x, y;
};
Graph *init_graph(int n)
{
Graph *graph = (Graph *)malloc(sizeof(Graph));
graph->adj = (gList **)calloc(n, sizeof(gList *));
graph->n = n;
return graph;
}
void add_arc(Graph *graph, int nod1, int nod2, int cost)
{
gList *nou = (gList *)malloc(sizeof(gList));
nou->cost = cost;
nou->nod = nod2;
nou->next = graph->adj[nod1];
graph->adj[nod1] = nou;
}
void free_graph(Graph *graph)
{
int i;
for (i = 0; i < graph->n; i++)
{
gList *p = graph->adj[i];
while (p)
{
gList *todel = p;
p = p->next;
free(todel);
}
}
free(graph->adj);
free(graph);
}
int get_cost(Graph *graph, int nod1, int nod2)
{
gList *p = graph->adj[nod1];
while (p)
{
if (p->nod == nod2)
return p->cost;
p = p->next;
}
return INT_MAX;
}
void dfs(Graph *graph, int nod, int *disc, int *low, int *time, int *parent, std::stack<Edge> *st, int *nr, std::vector<int> *biconex)
{
gList *p = graph->adj[nod];
disc[nod] = low[nod] = ++(*time);
//printf("%d\n", *time);
int children = 0;
while (p)
{
int i = p->nod;
if (disc[i] == -1)
{
parent[i] = nod;
children++;
Edge aux;
aux.x = nod;
aux.y = i;
st->push(aux);
dfs(graph, i, disc, low, time, parent, st, nr, biconex);
low[nod] = std::min(low[nod], low[i]);
if ((disc[nod] == 1 && children > 1) ||
(disc[nod] > 1 && low[i] >= disc[nod]))
{
int flag = 0;
while (st->top().x != nod || st->top().y != i)
{
flag = 1;
biconex[*nr].push_back(st->top().x);
st->pop();
}
if (flag)
{
//printf("%d\n", st->top().x + 1);
biconex[(*nr)++].push_back(st->top().x);
}
else
{
printf("%d %d\n", st->top().x + 1, st->top().y + 1);
biconex[*nr].push_back(st->top().x);
biconex[(*nr)++].push_back(st->top().y);
}
st->pop();
}
}
else
{
if (i != parent[nod])
{
low[nod] = std::min(low[nod], disc[i]);
if (disc[i] < disc[nod])
{
Edge aux;
aux.x = nod;
aux.y = i;
st->push(aux);
}
}
}
p = p->next;
}
}
int main()
{
FILE *in = fopen("biconex.in", "r");
FILE *out = fopen("biconex.out", "w");
int n, m;
fscanf(in, "%d", &n);
fscanf(in, "%d", &m);
Graph *graph = init_graph(n);
int *low = (int *)malloc(n * sizeof(int));
int *disc = (int *)malloc(n * sizeof(int));
int *parent = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
disc[i] = parent[i] = low[i] = -1;
int time = 0;
for (int i = 0; i < m; i++)
{
int nod1, nod2;
fscanf(in, "%d%d", &nod1, &nod2);
//printf("%d %d\n", nod1, nod2);
nod1--;
nod2--;
add_arc(graph, nod1, nod2, 1);
add_arc(graph, nod2, nod1, 1);
}
std::stack<Edge> st;
int nr = 0;
std::vector<int> biconex[100000];
dfs(graph, 0, disc, low, &time, parent, &st, &nr, biconex);
if (st.size() == 1)
{
biconex[nr].push_back(st.top().x);
biconex[nr].push_back(st.top().y);
}
else
{
while (!st.empty())
{
biconex[nr].push_back(st.top().x);
st.pop();
}
}
nr++;
fprintf(out, "%d\n", nr);
for (int i = 0; i < nr; i++)
{
for (int j = 0; j < biconex[i].size(); j++)
{
fprintf(out, "%d ", biconex[i][j] + 1);
}
fprintf(out, "\n");
}
free(low);
free(disc);
free(parent);
free_graph(graph);
fclose(in);
fclose(out);
return 0;
}