// bibliotecile necesare
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
// fisierele din care scriu si citesc
ifstream fin("biconex.in");
ofstream fout("biconex.out");
// lista de adicenta a grafului la care adaug si id-ul muchie catre vecin
vector<pair<int, int>> graf[100001];
int disc[100001] = {}; // in disc[nod] retin momentul descoperirii nodului
int low[100001] = {}; // low[nod] retine cea mai mic timp descoperit accesibil din subaroborele dfs al nodului
int timp = 0; // contor pentru momentul descoperirii
stack<pair<int,int>> stiva; // ma folosesc de o stiva pentru a memora muchiile intalnite in dfs (nod, vecin)
vector<vector<int>> solutie; // in solutie retin componentele biconexe identificate
// implementez o functie dfs cu 2 argumente ( nodul curent si id-ul muchie parinte)
void dfs(int nod, int muchieParinte){
disc[nod] = low[nod] = ++timp; // initializez disc[nod] si low[nod] cu timp( momentul descoperirii )
// parcurg vecinii nodului
for(auto p : graf[nod]){
int vecin = p.first;
int id = p.second;
if(id == muchieParinte){ // ignor muchia prin care ajungem in nodul curent
continue;
}
// daca nu am mai intalnit nodul
if(disc[vecin] == 0){
stiva.push({nod, vecin}); // adaug in stiva perechea {nod, vecin} ce reprezinta muchia dintre cele 2 noduri
dfs(vecin, id); // aplic dfs pentru vecin
low[nod] = min(low[nod], low[vecin]); // dupa ce ies din dfs, actualizez low[nod]
if(low[vecin] >= disc[nod]){ // subarborele lui vecin nu poate ajunge la un stramos al lui nod printr- o muchie de intoarcere
vector<int> componenta; // memorez nodurile componentei biconexe curente
// putem forma acum o componenta biconexa
while(!stiva.empty()){ // cat timp nu am stiva goala
int a = stiva.top().first; // citesc nodul
int b = stiva.top().second; // si vecinul sau
stiva.pop(); // si elimin perechea
// le adaug acum in componenta curenta
componenta.push_back(a);
componenta.push_back(b);
if(a == nod && b == vecin){ // pana cand ajung la muchia de la care a inceput ramura
break;
}
}
// pentru ca in momentul in care scoatem muchiile, adaugam abele capete in vector
// trebuie sa pastrez fiecare nod o singura data
sort(componenta.begin(), componenta.end()); // le ordonez crescator
componenta.erase( // elimin duplicatele
unique(componenta.begin(), componenta.end()),
componenta.end()
);
solutie.push_back(componenta); // adaug coponenta in solutie
}
}
else if (disc[vecin] < disc[nod]){ // am gasit o muchie de intoarcere catre un stramos din arborele dfs
stiva.push({nod, vecin}); // adaug si muchia (nod, vecin)
low[nod] = min(low[nod], disc[vecin]); // actualizam low[nod]
}
}
}
int main(){
// introduc numarul de noduri si muchii
int n, m;
fin >> n >> m;
// formez lista de adiacenta
for(int i = 1; i <= m ; i++){
int a, b;
fin >> a >> b;
graf[a].push_back({b, i});
graf[b].push_back({a,i});
}
// rulez pentru fiecare nod nevizitat dfs-ul
for(int i = 1; i <= n; i++){
if(disc[i] == 0){
dfs(i, -1);
}
}
// afisez solutiile
fout << solutie.size() << '\n';
for(auto componenta : solutie){
for(int nod : componenta){
fout << nod << " ";
}
fout << '\n';
}
return 0;
}