/*
* @ Copyright, 25.04.2010
* Mihai Tabara
* 325 CA
* Bonus Lab 7
* Time Complexity - O(N + M)
* Language used: C++
*/
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const char *in = "biconex.in";
const char *out = "biconex.out";
const int DIM = 2800000;
const int NMAX = 100005;
typedef vector<int>::iterator IT;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
template <class T>
T minim (T a, T b)
{
return ((a) < (b) ? (a) : (b));
}
int N, M;
VI L[NMAX], level, low;
VVI SOL;
stack< pair<int,int> > st;
void Push (const int, const int);
void DF (int,int,int);
int main(void)
{
freopen (in, "r", stdin);
freopen (out, "w", stdout);
char buf[DIM];
int X, Y, poz;
/* Parsing the input reading */
fread (buf, 1, DIM, stdin);
#define cit(x) \
{ \
x = 0; \
while (buf[poz] < '0') \
{ \
++poz; \
if (poz == DIM) { \
fread (buf, 1, DIM, stdin); poz = 0; } \
} \
while (buf[poz] >= '0') \
{ \
x = x*10 + buf[poz] - '0'; \
if (++poz == DIM) { \
fread (buf, 1, DIM, stdin); poz = 0; } \
} \
}
cit(N) cit(M)
for ( ; M; --M)
{
cit(X) cit(Y)
L[X].push_back (Y);
L[Y].push_back (X);
}
level.resize (N + 1);
level.assign (N + 1, -1);
low.resize (N+1);
DF (1,0,0);
size_t i = SOL.size(), j;
printf ("%d\n", i);
for (i = 0; i < SOL.size(); ++i)
{
sort (SOL[i].begin(), SOL[i].end());
SOL[i].erase (unique (SOL[i].begin(), SOL[i].end()), SOL[i].end()); /* elimin duplicatele din vector ( am inserat muchii deci vor if noduri care se repeta */
for (j = 0; j < SOL[i].size(); ++j)
printf ("%d ", SOL[i][j]); /* afisez o componenta biconexa */
printf ("\n");
}
return 0;
}
void Push (const int X, const int Y)
{
VI tmp;
int x, y;
do
{
x = st.top().first, y = st.top().second;
st.pop();
tmp.push_back(x), tmp.push_back(y);
} while (x != X || y != Y ); /* elimin din stiva toate muchiile pana la muchia (X,Y) inclusiv */
SOL.push_back (tmp); /* muchiile eliminate formeaza o componenta biconexa */
}
void DF (int nod, int fnod, int niv)
{
IT it;
level[nod] = low[nod] = niv; /* current level, lowest level */
for (it = L[nod].begin(); it != L[nod].end(); ++it)
{
if (*it == fnod) continue;
if (level[*it] == -1) /* muchie de arbore */
{
st.push(make_pair (nod, *it));
DF (*it, nod, niv+1);
low[nod] = minim (low[nod], low[*it]);
if (low[*it] >= level[nod] ) /* nod - punct de articulatie */
Push (nod, *it);
}
else
low[nod] = minim (low[nod], level[*it]); /* muchie de intoarcere */
}
}