#include <stdio.h>
#include <stdlib.h>
#define Smerenie 400001
#define Nadejde 100001
typedef struct {
int v, next;
} list;
typedef struct {
int u, v;
} cell;
int N, M, ss;
int buff = 1;
int d[Nadejde];
int low[Nadejde];
int adj[Nadejde];
list l[Smerenie];
list com[Smerenie];
cell stack[Smerenie];
int numSeen, adjb[Nadejde];
int freq[Nadejde], *bcc[Nadejde];
/** Adauga-l pe "v" la lista de adiacenta a lui "u". **/
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
/** Adauga-l pe "u" la componenta curenta. **/
void put(int u) {
com[buff].v = u;
com[buff].next = adjb[numSeen];
adjb[numSeen] = buff++;
}
/** Pune in stiva muchia (u, v). **/
void push(int u, int v) {
stack[ss].u = u;
stack[ss++].v = v;
}
/** Formeaza componenta curenta. **/
void getBcc(int u, int v) {
cell tmp;
numSeen++;
do {
tmp = stack[--ss];
freq[numSeen] += 2;
put(tmp.u), put(tmp.v);
} while ((u != tmp.u) || (v != tmp.v));
}
/** Exploreaza graful, determinand componentele biconexe. **/
void dfs(int u, int parent, int depth) {
int v, pos;
low[u] = d[u] = depth;
for (pos = adj[u]; pos; pos = l[pos].next) {
v = l[pos].v;
if (v != parent) {
if (!d[v]) {
push(u, v);
dfs(v, u, depth + 1);
if (low[v] < low[u]) {
low[u] = low[v];
}
if (low[v] >= d[u]) {
getBcc(u, v);
}
} else if (d[v] < low[u]) {
low[u] = d[v];
}
}
}
}
/** Aloca un vector de marimea "size" pentru componenta curenta. **/
void alloc(int *size) {
bcc[buff] = (int*)calloc(*size, sizeof(int));
(*size) = 0;
}
/** Sorteaza crescator nodurile din componenta curenta. **/
void sort(int begin, int end) {
int b = begin, e = end, pivot = bcc[buff][(b + e) >> 1];
while (b <= e) {
while (bcc[buff][b] < pivot) {
b++;
}
while (bcc[buff][e] > pivot) {
e--;
}
if (b <= e) {
int tmp = bcc[buff][b];
bcc[buff][b++] = bcc[buff][e];
bcc[buff][e--] = tmp;
}
}
if (b < end) {
sort(b, end);
}
if (begin < e) {
sort(begin, e);
}
}
/** Sterge dublurile din componenta. **/
void unique(int n) {
int i = 0;
sort(0, n - 1);
while (i < n) {
int j = i + 1;
while ((j < n) && (bcc[buff][j] == bcc[buff][i])) {
bcc[buff][j++] = 0;
}
i = j;
}
}
/** Construieste componentele biconexe. **/
void biconex() {
int pos;
dfs(1, 0, 1);
for (buff = 1; buff <= numSeen; buff++) {
alloc(&freq[buff]);
for (pos = adjb[buff]; pos; pos = com[pos].next) {
bcc[buff][freq[buff]++] = com[pos].v;
}
unique(freq[buff]);
}
}
int main(void) {
int i, u, v;
FILE *f = fopen("biconex.in", "r");
/* Citeste graful. */
fscanf(f, "%d %d", &N, &M);
for (i = 1; i <= M; i++) {
fscanf(f, "%d %d", &u, &v);
addEdge(u, v, i);
addEdge(v, u, i + M);
}
fclose(f);
f = fopen("biconex.out", "w");
biconex();
fprintf(f, "%d\n", numSeen);
for (u = 1; u <= numSeen; u++) {
for (i = 0; i < freq[u]; i++) {
if (bcc[u][i]) {
fprintf(f, "%d ", bcc[u][i]);
}
}
fputc('\n', f);
}
fclose(f);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}