#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define NMAX 100001
#define MMAX 1000005
class Graf{
vector<int> nod[NMAX];
vector<int> viz;
vector<int> nma;
vector<int> nivel;
queue<int> coada;
stack<int> stiva;
vector<vector<int>> componente;
int nrNoduri, nrMuchi;
bool orientat = false, neorientat = false;
void setOrientat(bool orientat = true){
if(orientat) this->orientat = true, this->neorientat = false;
else this->orientat = false, this->neorientat = true;
}
void setNeorientat(bool neorientat = true){
if(neorientat) this->neorientat = true, this->orientat = false;
else this->neorientat = false, this->orientat = true;
}
void setViz(int nod, int val){
this->viz.assign(nod + 1, val);
}
void actBFS(int S);
void actDFS(int S);
void biconexeDFS(int S, int Tata);
public:
void citire(int nrNoduri, int nrMuchi, vector<pair<int, int>> muchi, bool orientat = true){
if(orientat) setOrientat();
else setNeorientat();
this->nrNoduri = nrNoduri;
this->nrMuchi = nrMuchi;
for(auto i : muchi){
this->nod[i.first].push_back(i.second);
if(this->neorientat) this->nod[i.second].push_back(i.first);
}
}
vector<int> BFS(int S);
int DFS();
vector<vector<int>> compBiconexe();
};
Graf graf;
void Graf::actBFS(int S){
this->coada.push(S);
this->viz[S] = 0;
while(!coada.empty()){
int current = coada.front();
coada.pop();
int dist = viz[current] + 1;
for(auto vecin : nod[current]){
if(viz[vecin] == -1){
viz[vecin] = dist;
coada.push(vecin);
}
}
}
}
vector<int> Graf::BFS(int S){
setViz(this->nrNoduri, -1);
actBFS(S);
return this->viz;
}
void Graf::actDFS(int S){
viz[S] = 1;
for(auto vecini : nod[S]){
if(!viz[vecini]) actDFS(vecini);
}
}
int Graf::DFS(){
int componente = 0;
setViz(nrNoduri, 0);
for(int i = 1; i <= nrNoduri; i++){
if(!viz[i]) actDFS(i), ++componente;
}
return componente;
}
void Graf::biconexeDFS(int S, int Tata){
viz[S] = 1;
nma[S] = nivel[S] = nivel[Tata] + 1;
stiva.push(S);
for(auto vecin : nod[S]){
if(vecin != Tata){
if(viz[vecin]){
nma[S] = min(nma[S], nivel[vecin]);
}
else{
biconexeDFS(vecin, S);
nma[S] = min(nma[S], nma[vecin]);
if(nivel[S] <= nma[vecin]){
vector<int> comp;
while(stiva.top() != vecin){
comp.push_back(stiva.top());
stiva.pop();
}
comp.push_back(vecin);
stiva.pop();
comp.push_back(S);
componente.push_back(comp);
}
}
}
}
}
vector<vector<int>> Graf::compBiconexe(){
viz.assign(nrNoduri+1, 0);
nivel.assign(nrNoduri+1, 0);
nma.assign(nrNoduri+1, 0);
biconexeDFS(1,0);
return componente;
}
void rezolvareBFS(){
vector<pair<int, int>> muchi;
int n, m, s;
fin>>n>>m>>s;
for(int i = 1; i <= m; i++){
int x, y;
fin>>x>>y;
muchi.push_back(make_pair(x, y));
}
graf.citire(n, m, muchi);
vector<int> sol = graf.BFS(s);
for(int i = 1; i <= n; i++){
fout<<sol[i]<<" ";
}
}
void rezolvareDFS(){
vector<pair<int, int>> muchi;
int n, m;
fin>>n>>m;
for(int i = 1; i <= m; i++){
int x, y;
fin>>x>>y;
muchi.push_back(make_pair(x, y));
}
graf.citire(n, m, muchi, false);
int res = graf.DFS();
fout<<res;
}
void rezolvareBiconexe(){
vector<pair<int, int>> muchi;
int n, m;
fin>>n>>m;
for(int i = 1; i <= m; i++){
int x, y;
fin>>x>>y;
muchi.push_back(make_pair(x, y));
}
graf.citire(n, m, muchi, false);
vector<vector<int>> sol = graf.compBiconexe();
int nrComp = sol.size();
fout<<nrComp<<'\n';
for(int i = 0; i < nrComp; i++)
{
for(auto nod : sol[i])
fout<<nod<<' ';
fout<<'\n';
}
}
int main(){
rezolvareBiconexe();
}