#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class Graf {
int nrNoduri, nrMuchii;
bool eOrientat, arePonderi;
vector<int> *adiacenta; // lista de vecini
public:
Graf(int nrNoduri, const bool eOrientat, const bool arePonderi);
void citire(const int nrMuchii);
void rezolvaBiconex();
private:
void biconex(int nodPlecare, int precedent, int k, stack<pair<int, int>> &stivaComponenteBiconexe,
vector<set<int>> &componenteBiconexe, vector<int> &vizitat, vector<int> &niv_min);
};
void Graf::biconex(int nodPlecare, int precedent, int k, stack<pair<int, int>> &stivaComponenteBiconexe,
vector<set<int>> &componenteBiconexe, vector<int> &vizitat, vector<int> &niv_min) {
vizitat[nodPlecare] = k;
niv_min[nodPlecare] = k;
for (auto &i: adiacenta[nodPlecare]) {
int vecin = i;
if (vecin != precedent) { // pentru optimizare (iese din timp altfel, uneori),
// daca vecinul curent nu s-a executat la pasul anterior
if (!vizitat[vecin]) { // daca vecinul nu a fost vizitat
stivaComponenteBiconexe.push(make_pair(nodPlecare, vecin));
biconex(vecin, nodPlecare, k + 1, stivaComponenteBiconexe, componenteBiconexe, vizitat,
niv_min); // reapelez DF din nodul in care am ajuns
if (niv_min[nodPlecare] > niv_min[vecin]) // daca face parte din ciclu
niv_min[nodPlecare] = niv_min[vecin]; // actualizez nivelul minim
if (niv_min[vecin] >= vizitat[nodPlecare]) {
// daca un vecin are nivelul minim mai mare sau egal decat nivelul tatalui sau
// (vizitat este pe pos de nivel din muchia critica, i.e. nivelul din arborele DF),
// inseamna ca nu face parte dintr-un ciclu, deci am gasit o componenta biconexa
set<int> aux;
int aux1, aux2;
do {
aux1 = stivaComponenteBiconexe.top().first;
aux2 = stivaComponenteBiconexe.top().second;
aux.insert(aux1);
aux.insert(aux2);
stivaComponenteBiconexe.pop();
} while (aux1 != nodPlecare || aux2 != vecin);
componenteBiconexe.push_back(aux);
}
} else if (niv_min[nodPlecare] > vizitat[vecin]) { // daca nodul curent a fost deja vizitat
// si daca exista o muchie de intoarcere de la nodPlecare la nodul curent, exista legatura cu un stramos
// (muchie de intoarcere de la nodPlecare la nodul curent)
niv_min[nodPlecare] = vizitat[vecin]; // nivelul nodului de Plecare
// va fi nivelul stramosului sau (nodul deja vizitat)
}
}
}
}
void Graf::rezolvaBiconex() {
stack<pair<int, int>> stivaComponenteBiconexe;
vector<set<int>> componenteBiconexe;
vector<int> vizitat(nrNoduri + 1, 0);
vector<int> niv_min(nrNoduri + 1, 0);
biconex(1, 0, 1, stivaComponenteBiconexe, componenteBiconexe, vizitat, niv_min);
set<int>::iterator it;
fout << componenteBiconexe.size() << "\n";
for (auto &i: componenteBiconexe) {
for (it = i.begin(); it != i.end(); it++) {
fout << *it << " ";
}
fout << "\n";
}
}
int main() {
int nrNoduri, nrMuchii;
fin >> nrNoduri >> nrMuchii;
Graf g1(nrNoduri, false, false);
g1.citire(nrMuchii);
g1.rezolvaBiconex();
fin.close();
fout.close();
return 0;
}
void Graf::citire(const int nrMuchii) {
int sursa, destinatie; // extremitate muchie stanga respectiv dreapta
adiacenta = new vector<int>[nrNoduri + 1];
if (!arePonderi) {
if (eOrientat)
for (int i = 1; i <= nrMuchii; i++) {
fin >> sursa >> destinatie;
adiacenta[sursa].push_back(destinatie);
}
else
for (int i = 1; i <= nrMuchii; i++) {
fin >> sursa >> destinatie;
adiacenta[sursa].push_back(destinatie);
adiacenta[destinatie].push_back(sursa);
}
}
}
Graf::Graf(int nrNoduri, const bool eOrientat, const bool arePonderi) {
this->nrNoduri=nrNoduri;
this->eOrientat=eOrientat;
this->arePonderi=arePonderi;
}