#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
class Graph{
private:
int n;
vector < vector<int> > la;
vector<vector<int>> componente_biconexe;
vector<vector<int>> componente_tconexe;
vector<int> lowest, level, father, degrees;
vector<bool> onstack;
stack<int> S;
stack<pair<int,int>> edges_biconexe;
int index;
void dfs(int nod_crt, vector<bool> &viz);
void dfs_biconexe(int nod_crt);
void dfs_tarjan(int nod_crt);
void add_cmp_biconexa(int x, int y);
bool consume(int nr, int poz);
public:
Graph(int nr_noduri):n(nr_noduri), la(nr_noduri+1), componente_biconexe(0), componente_tconexe(0), lowest(0), level(0), father(0), onstack(0), index(0), degrees(0){}
~Graph() = default;
void add_edge(int from, int to){
la[from].push_back(to);
}
void bfs_print_dist(int start=1); // Starting from node 1
int nr_conexe_dfs();
void print_sortare_topologica(ostream &out);
void print_comp_biconexe_udg(ostream &out);
void print_comp_tconexe_dg(ostream &out);
bool Havel_Hakimi(vector<int> &grade_noduri);
};
void Graph::bfs_print_dist(int start)
{
vector<int> dist(n+1,0);
queue<int> q;
int nod_crt;
q.push(start);
dist[start]=1;
while(!q.empty())
{
nod_crt = q.front();
q.pop();
for(auto nod_vecin: la[nod_crt])
{
if(dist[nod_vecin] == 0)
{
dist[nod_vecin] = dist[nod_crt] + 1;
q.push(nod_vecin);
}
}
}
for(int i=1;i<=n;++i)
g<<dist[i]-1<<' ';
}
int Graph::nr_conexe_dfs()
{
vector<bool> viz(n+1, false);
int nr_c=0;
for(int i=1;i<=n;++i)
{
if(!viz[i])
{
++nr_c;
dfs(i, viz);
}
}
return nr_c;
}
void Graph::print_sortare_topologica(ostream &out)
{
queue<int> zero_nodes;
degrees.resize(n+1,0);
int nod_curent, i;
for(i=1;i<=n;++i)
{
for(auto nod_vecin: la[i])
++degrees[nod_vecin];
}
for(i=1; i<=n;++i)
if(degrees[i] == 0)
zero_nodes.push(i);
if(zero_nodes.empty())
{
cout<<"Cyclic Graph. Can't sort.";
return;
}
while(!zero_nodes.empty())
{
nod_curent = zero_nodes.front();
zero_nodes.pop();
out<<nod_curent<<' ';
for(auto nod_vecin: la[nod_curent])
{
--degrees[nod_vecin];
if(degrees[nod_vecin] == 0)
zero_nodes.push(nod_vecin);
}
}
degrees.clear();
}
void Graph::dfs(int nod_crt, vector<bool> &viz)
{
for(auto nod_vecin: la[nod_crt])
{
if(!viz[nod_vecin])
{
viz[nod_vecin] = true;
dfs(nod_vecin, viz);
}
}
}
void Graph::add_cmp_biconexa(int x, int y)
{
int a,b;
vector<int> componenta_biconexa;
do
{
a=edges_biconexe.top().first;
b=edges_biconexe.top().second;
edges_biconexe.pop();
componenta_biconexa.push_back(a);
componenta_biconexa.push_back(b);
}while((a!=x || b!=y) && !edges_biconexe.empty());
sort(componenta_biconexa.begin(), componenta_biconexa.end() );
componente_biconexe.push_back(componenta_biconexa);
}
void Graph::dfs_biconexe(int nod_crt)
{
level[nod_crt] = level[father[nod_crt]] + 1;
lowest[nod_crt] = level[nod_crt];
for(auto nod_vecin: la[nod_crt])
{
if(level[nod_vecin] == 0)
{
father[nod_vecin] = nod_crt;
edges_biconexe.push(make_pair(nod_crt, nod_vecin));
dfs_biconexe(nod_vecin);
if(lowest[nod_vecin] >= level[nod_crt])
add_cmp_biconexa(nod_crt, nod_vecin);
lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
}
else if(nod_vecin!= father[nod_crt])
lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);;
}
}
void Graph::print_comp_biconexe_udg(ostream &out)
{
lowest.resize(n+1, 0);
level.resize(n+1, 0);
father.resize(n+1, 0);
dfs_biconexe(1);
out<<componente_biconexe.size()<<'\n';
for(auto componenta:componente_biconexe)
{
out<<componenta[0];
for(int i=1;i<componenta.size();++i)
if(componenta[i]!=componenta[i-1])
out<<' '<<componenta[i];
out<<'\n';
}
lowest.clear();
level.clear();
father.clear();
}
void Graph::dfs_tarjan(int nod_crt)
{
++index;
level[nod_crt] = index;
lowest[nod_crt] = index;
S.push(nod_crt);
onstack[nod_crt] = true;
for(auto nod_vecin : la[nod_crt])
{
if(level[nod_vecin]==0)
{
dfs_tarjan(nod_vecin);
lowest[nod_crt] = min(lowest[nod_crt], lowest[nod_vecin]);
}
else if(onstack[nod_vecin])
lowest[nod_crt] = min(lowest[nod_crt], level[nod_vecin]);
}
if(level[nod_crt] == lowest[nod_crt])
{
vector<int> comp_tconexa;
int st;
do
{
st = S.top();
S.pop();
onstack[st]=false;
comp_tconexa.push_back(st);
}while(st!=nod_crt);
componente_tconexe.push_back(comp_tconexa);
}
}
void Graph::print_comp_tconexe_dg(ostream &out)
{
onstack.resize(n+1, false);
lowest.resize(n+1, 0);
level.resize(n+1, 0);
for(int i=1;i<=n;++i)
{
if(level[i] == 0)
{
dfs_tarjan(i);
}
}
out<<componente_tconexe.size()<<'\n';
for(auto comp: componente_tconexe)
{
for(auto nod:comp)
out<<nod<<' ';
out<<'\n';
}
onstack.clear();
lowest.clear();
level.clear();
}
bool Graph::consume(int nr, int poz)
{
if(nr == 0)
return true;
if(poz == 0)
return false;
if(nr>degrees[poz])
{
bool ok = consume(n-degrees[poz], poz-1);
degrees[poz-1]+=degrees[poz];
degrees[poz]=0;
return ok;
}
degrees[poz-1]+=nr;
degrees[poz] -=nr;
return true;
}
bool Graph::Havel_Hakimi(vector<int>& grade_noduri)
{
int sum=0, max_grade = 0;
degrees.resize(n, 0);
for(auto x: grade_noduri)
{
if(x>=n)
{
degrees.clear();
return false;
}
++degrees[x];
sum+=x;
if(x>max_grade)
max_grade = x;
}
if( sum & 1)
{
degrees.clear();
return false;
}
if(max_grade <=1 )
{
degrees.clear();
return true;
}
for(int i=max_grade; i; --i)
{
while(degrees[i])
{
--degrees[i];
if( !consume(i, i) )
{
degrees.clear();
return false;
}
}
}
degrees.clear();
return true;
}
int get_degrees(const char* f_name, vector<int>& v)
{
ifstream in(f_name);
int n,m,a,b;
in>>n>>m;
v.resize(n, 0);
for(int i=0;i<m;++i)
{
f>>a>>b;
++v[a-1];
++v[b-1];
}
}
int main()
{
int n,m;
int a,b;
f>>n;
f>>m;
Graph gr(n);
for(int i=0;i<m;++i)
{
f>>a>>b;
gr.add_edge(a,b);
gr.add_edge(b,a);
}
f.close();
gr.print_comp_biconexe_udg(g);
g.close();
return 0;
}