#include<iostream>
#include<vector>
#include <queue>
#include<stack>
#include <utility>
#include<algorithm>
#include<fstream>
using namespace std;
class Graf { ///clasa abstracta graf
public:
	virtual void citire(istream& in) = 0;
	virtual void afisare(ostream& out) = 0;
};
class Graf_orientat : public Graf ///graf orientat
{
private:
	int Nr_noduri, Nr_muchii;
	vector<vector<int>>Lista_de_adiacenta;
public:
	Graf_orientat(int, int, vector<vector<int>>);
	~Graf_orientat();
	void adauga_in_lista_de_adiacenta(int, int);
	void citire(istream& in);
	void afisare(ostream& out);
	friend istream& operator >>(istream&, Graf_orientat&);
	friend ostream& operator <<(ostream&, Graf_orientat&);
	vector<int> BFS(int);
	vector<int> Sortare_topologica();

};

Graf_orientat::Graf_orientat(int Nr_noduri = 0, int Nr_muchii = 0, vector<vector<int>>Lista_de_adiacenta = {}) {
	this->Nr_noduri = Nr_noduri;
	this->Nr_muchii = Nr_muchii;
	this->Lista_de_adiacenta.resize(Nr_noduri + 1);
	for (int i = 1; i < Lista_de_adiacenta.size(); i++)
		for (int j = 0; j < Lista_de_adiacenta[i].size(); j++)
			this->Lista_de_adiacenta[i].push_back(Lista_de_adiacenta[i][j]);
}

void Graf_orientat::adauga_in_lista_de_adiacenta(int nod_stang, int nod_drept) {
	this->Lista_de_adiacenta[nod_stang].push_back(nod_drept);
}

void Graf_orientat::citire(istream& in) {

	in >> Nr_noduri;
	in >> Nr_muchii;
	this->Lista_de_adiacenta.resize(Nr_noduri + 1);
	int stanga, dreapta;
	for (int i = 1; i <= Nr_muchii; i++)
	{
		in >> stanga;
		in >> dreapta;
		adauga_in_lista_de_adiacenta(stanga, dreapta);
	}

}

void Graf_orientat::afisare(ostream& out) {

	out << Nr_noduri << " ";
	out << Nr_muchii << endl;
	for (int i = 1; i < Lista_de_adiacenta.size(); i++) {
		for (int j = 0; j < Lista_de_adiacenta[i].size(); j++)
			out << i << " " << Lista_de_adiacenta[i][j] << " ";
	}
}

istream& operator>>(istream& in, Graf_orientat& g)
{
	g.citire(in);
	return in;
}
ostream& operator<<(ostream& out, Graf_orientat& g)
{
	g.afisare(out);
	return out;
}

Graf_orientat::~Graf_orientat() {
	this->Lista_de_adiacenta.clear();
	this->Nr_muchii = 0;
	this->Nr_noduri = 0;

}

vector<int> Graf_orientat::BFS(int Start_nod) {
	vector<int>Distante(this->Nr_noduri + 1, -1);
	deque<int>coada;
	coada.push_back(Start_nod);
	Distante[Start_nod] = 0;

	while (!coada.empty()) {
		int primul_nod_din_coada = coada.front();
		for (int i = 0; i < Lista_de_adiacenta[primul_nod_din_coada].size(); i++) {
			int nod_curent = Lista_de_adiacenta[primul_nod_din_coada][i];
			if (Distante[nod_curent] == -1) {
				coada.push_back(nod_curent);
				Distante[nod_curent] = Distante[primul_nod_din_coada] + 1;
			}
		}
		coada.pop_front();
	}
	return Distante;
}

class Graf_neorientat : public Graf   ///graf neorientat
{
private:
	int Nr_noduri, Nr_muchii;
	vector<vector<int>>Lista_de_adiacenta;
public:
	Graf_neorientat(int, int, vector<vector<int>>);
	~Graf_neorientat();
	int get_nr_noduri();
	void adauga_in_lista_de_adiacenta(int, int);
	void citire(istream& in);
	void afisare(ostream& out);
	friend istream& operator >>(istream&, Graf_neorientat&);
	friend ostream& operator <<(ostream&, Graf_neorientat&);
	vector<int> BFS(int);
	void DFS(int, vector<int>&);
	void Afla_noduri_critice(int, vector<int>&, vector<int>&, vector<int>&, vector<int>&, vector<int>&);
	vector<int> ANC();
	void Parcurgere_comp_biconexe(int, vector<int>&, vector<int>&, vector<int>&, vector<int>&, stack<pair<int, int>>&, vector<vector<pair<int, int>>>&, int&);
	vector<vector<pair<int, int>>> Componente_biconexe(int&);

};

Graf_neorientat::Graf_neorientat(int Nr_noduri = 0, int Nr_muchii = 0, vector<vector<int>>Lista_de_adiacenta = {}) {
	this->Nr_noduri = Nr_noduri;
	this->Nr_muchii = Nr_muchii;
	this->Lista_de_adiacenta.resize(Nr_noduri + 1);

	for (int i = 1; i < Lista_de_adiacenta.size(); i++)
		for (int j = 0; j < Lista_de_adiacenta[i].size(); j++) {
			this->Lista_de_adiacenta[i].push_back(Lista_de_adiacenta[i][j]);
			this->Lista_de_adiacenta[j].push_back(Lista_de_adiacenta[i][j]);
		}
}

int Graf_neorientat::get_nr_noduri() {
	return Nr_noduri;
}

void Graf_neorientat::adauga_in_lista_de_adiacenta(int nod_stang, int nod_drept) {
	this->Lista_de_adiacenta[nod_stang].push_back(nod_drept);
}

void Graf_neorientat::citire(istream& in) {

	in >> Nr_noduri;
	in >> Nr_muchii;
	this->Lista_de_adiacenta.resize(Nr_noduri + 1);
	int stanga, dreapta;
	for (int i = 1; i <= Nr_muchii; i++)
	{
		in >> stanga;
		in >> dreapta;
		adauga_in_lista_de_adiacenta(stanga, dreapta);
		adauga_in_lista_de_adiacenta(dreapta, stanga);
	}

}

void Graf_neorientat::afisare(ostream& out) {

	out << Nr_noduri << " ";
	out << Nr_muchii << endl;
	for (int i = 1; i < Lista_de_adiacenta.size(); i++) {
		for (int j = 0; j < Lista_de_adiacenta[i].size(); j++)
			out << Lista_de_adiacenta[i][j] << " ";
	}
}

istream& operator>>(istream& in, Graf_neorientat& g)
{
	g.citire(in);
	return in;
}
ostream& operator<<(ostream& out, Graf_neorientat& g)
{
	g.afisare(out);
	return out;
}

Graf_neorientat::~Graf_neorientat() {
	this->Lista_de_adiacenta.clear();
	this->Nr_muchii = 0;
	this->Nr_noduri = 0;

}

void Graf_neorientat::DFS(int Nod_start, vector<int>& Vector_vizitati) {
	Vector_vizitati[Nod_start] = 0; ///Marcam nodul de unde incepe dfs-ul ca vizitat

	for (int i = 0; i < Lista_de_adiacenta[Nod_start].size(); i++)///parcurgem vecinii nodului
	{

		int nod_curent = Lista_de_adiacenta[Nod_start][i];
		if (Vector_vizitati[nod_curent] == -1)
			DFS(nod_curent, Vector_vizitati);
	}

}
int Numar_componente_conexe(Graf_neorientat g) {
	int Nr_noduri = g.get_nr_noduri();
	vector<int>Vector_vizitati(Nr_noduri + 1, -1); ///Marcam toate norudrile nevizitate
											   ///-1 =>nod nevizitat
											   ///0 =>nod vizitat
	int Nr_comp_conexe = 0;
	for (int i = 1; i <= Nr_noduri; i++)
	{
		if (Vector_vizitati[i] == -1) {    ///Daca nodul este nevizitat se aplica DFS
			g.DFS(i, Vector_vizitati);
			Nr_comp_conexe++;
		}
	}
	return Nr_comp_conexe;
}

void Graf_neorientat::Afla_noduri_critice(int Nod_start, vector<int>& Vector_vizitati, vector<int>& Timp_curent, vector<int>& Timp_min, vector<int>& Vector_tati,
	vector<int>& Noduri_critice) {
	static int timp_curent = 0;
	Vector_vizitati[Nod_start] = 0;
	int copii = 0;
	Timp_curent[Nod_start] = Timp_min[Nod_start] = ++timp_curent;
	for (int i = 0; i < Lista_de_adiacenta[Nod_start].size(); i++) {///parcurgem vecinii nodului
		int nod_curent = Lista_de_adiacenta[Nod_start][i];
		if (Vector_vizitati[nod_curent] == -1) {
			copii++;
			Vector_tati[nod_curent] = Nod_start;
			Afla_noduri_critice(nod_curent, Vector_vizitati, Timp_curent, Timp_min, Vector_tati, Noduri_critice);
			Timp_min[Nod_start] = min(Timp_min[Nod_start], Timp_min[nod_curent]);
			if (Vector_tati[Nod_start] == 0 && copii > 1)///daca e radacina si are mai mult de un copil
				Noduri_critice.push_back(Nod_start);
			if (Vector_tati[Nod_start] != 0 && Timp_min[nod_curent] >= Timp_curent[Nod_start])///daca nu e radacina si fiul are gradul de intoarcere >= decat nivelul nodului
				Noduri_critice.push_back(Nod_start);
		}
		else
			if (nod_curent != Vector_tati[Nod_start])///actualizam distantele minime
				Timp_min[Nod_start] = min(Timp_min[Nod_start], Timp_curent[nod_curent]);
	}
}

void Graf_neorientat::Parcurgere_comp_biconexe(int Nod_start, vector<int>& Vector_vizitati, vector<int>& Timp_curent, vector<int>& Timp_min, vector<int>& Vector_tati,
	stack<pair<int, int>>& Stiva, vector<vector<pair<int, int>>>& Componente_biconexe, int& Nr_componente_biconexe) {

	Vector_vizitati[Nod_start] = 1;

	static int timp_curent = 0;
	int copii = 0;
	Timp_curent[Nod_start] = Timp_min[Nod_start] = ++timp_curent;
	for (int i = 0; i < Lista_de_adiacenta[Nod_start].size(); i++) {///parcurgem vecinii nodului
		int nod_curent = Lista_de_adiacenta[Nod_start][i];
		if (Vector_vizitati[nod_curent] == -1) {
			copii++;
			Vector_tati[nod_curent] = Nod_start;
			pair<int, int>Muchii;
			Muchii.first = Nod_start;
			Muchii.second = nod_curent;
			Stiva.push(Muchii);
			Parcurgere_comp_biconexe(nod_curent, Vector_vizitati, Timp_curent, Timp_min, Vector_tati, Stiva, Componente_biconexe, Nr_componente_biconexe);
			Timp_min[Nod_start] = min(Timp_min[Nod_start], Timp_min[nod_curent]);
			if ((Timp_curent[Nod_start] == 1 && copii > 1) || (Timp_curent[Nod_start] > 1 && Timp_min[nod_curent] >= Timp_curent[Nod_start])) {  ///daca e nod critic scot din stiva
				while ((Stiva.top().first != Nod_start || Stiva.top().second != nod_curent) && (Stiva.top().first != nod_curent || Stiva.top().second != Nod_start)) {
					pair<int, int>Muchii;
					Muchii.first = Stiva.top().first;
					Muchii.second = Stiva.top().second;
					Componente_biconexe[Nr_componente_biconexe].push_back(Muchii);
					Stiva.pop();
				}

				pair<int, int>Muchii;
				Muchii.first = Stiva.top().first;
				Muchii.second = Stiva.top().second;
				Componente_biconexe[Nr_componente_biconexe].push_back(Muchii);
				Stiva.pop();
				Nr_componente_biconexe++;
			}
		}
		else
			if (nod_curent != Vector_tati[Nod_start]) { ///actualizam distantele minime
				Timp_min[Nod_start] = min(Timp_min[Nod_start], Timp_curent[nod_curent]);

				if (Timp_curent[nod_curent] < Timp_curent[Nod_start]) {
					pair<int, int>Muchii;
					Muchii.first = Nod_start;
					Muchii.second = nod_curent;
					Stiva.push(Muchii);

				}
			}
	}
}

vector<int> Graf_neorientat::ANC() {
	vector<int>Noduri_critice;
	vector<int>Vector_vizitati(Nr_noduri + 1, -1);
	vector<int>Timp_curent(Nr_noduri + 1);
	vector<int>Timp_min(Nr_noduri + 1);
	vector<int>Vector_tati(Nr_noduri + 1, 0);

	for (int i = 1; i < Lista_de_adiacenta.size(); i++)
		if (Vector_vizitati[i] == -1)
			Afla_noduri_critice(i, Vector_vizitati, Timp_curent, Timp_min, Vector_tati, Noduri_critice);

	return Noduri_critice;
}

vector<vector<pair<int, int>>> Graf_neorientat::Componente_biconexe(int& Nr_comp_bi) {
	int Nr_comp_biconexe = 0;
	vector<vector<pair<int, int>>>Componente_biconexe(Nr_noduri);
	stack <pair<int, int>>Stiva;
	vector<int>Vector_vizitati(Nr_noduri + 1, -1);
	vector<int>Timp_curent(Nr_noduri + 1, -1);
	vector<int>Timp_min(Nr_noduri + 1, -1);
	vector<int>Vector_tati(Nr_noduri + 1, -1);
	for (int i = 1; i < Lista_de_adiacenta.size(); i++) {
		if (Vector_vizitati[i] == -1)
			Parcurgere_comp_biconexe(i, Vector_vizitati, Timp_curent, Timp_min, Vector_tati, Stiva, Componente_biconexe, Nr_comp_biconexe);
		int verifica = 0;
		while (Stiva.size() > 0) {
			verifica = 1;
			pair<int, int>Muchii;
			Muchii.first = Stiva.top().first;
			Muchii.second = Stiva.top().second;
			Componente_biconexe[Nr_comp_biconexe].push_back(Muchii);
			Stiva.pop();
		}

		if (verifica == 1) {
			Nr_comp_biconexe++;
		}
	}
	Nr_comp_bi = Nr_comp_biconexe;
	return Componente_biconexe;
}

vector<int> Graf_orientat::Sortare_topologica() {
	vector<int>Rezultat;
	vector<int>Vector_dependente(Nr_noduri + 1, 0);
	queue<int>Coada;
	for (int i = 1; i < Lista_de_adiacenta.size(); i++)
		for (int j = 0; j < Lista_de_adiacenta[i].size(); j++)
			Vector_dependente[Lista_de_adiacenta[i][j]]++;
	for (int i = 1; i < Vector_dependente.size(); i++)
		if (Vector_dependente[i] == 0)
			Coada.push(i);

	while (!Coada.empty())
	{
		int nod_curent = Coada.front();
		Rezultat.push_back(nod_curent);
		Coada.pop();
		for (int j = 0; j < Lista_de_adiacenta[nod_curent].size(); j++)
		{
			Vector_dependente[Lista_de_adiacenta[nod_curent][j]]--;
			if (Vector_dependente[Lista_de_adiacenta[nod_curent][j]] == 0)
				Coada.push(Lista_de_adiacenta[nod_curent][j]);
		}
	}
	return Rezultat;
}

void BFS_infoarena() {///BFS - PROBLEMA INFOARENA
	ifstream f_in("bfs.in");
	ofstream f_out("bfs.out");

	int Nr_noduri, Nr_muchii, Start_nod, Nod_st, Nod_dr;
	f_in >> Nr_noduri;
	f_in >> Nr_muchii;
	f_in >> Start_nod;
	vector<vector<int>>Lista_de_adiacenta(Nr_noduri + 1);

	for (int i = 0; i < Nr_muchii; i++)
	{
		f_in >> Nod_st >> Nod_dr;
		Lista_de_adiacenta[Nod_st].push_back(Nod_dr);
	}

	Graf_orientat graf(Nr_noduri, Nr_muchii, Lista_de_adiacenta);

	vector<int> Distante = graf.BFS(Start_nod);
	for (int i = 1; i < Distante.size(); i++)
		f_out << Distante[i] << " ";
	f_in.close();
	f_out.close();
	Lista_de_adiacenta.clear();
}

void DFS_infoarena() {
	ifstream f_in("dfs.in");
	ofstream f_out("dfs.out");
	Graf_neorientat graf;
	f_in >> graf;
	f_out << Numar_componente_conexe(graf);
	f_in.close();
	f_out.close();
}
void Sortare_vector_perechi(vector<vector<pair<int, int>>>& Comp_biconexe, int Numar_comp_biconexe) {
	for (int i = 0; i < Numar_comp_biconexe; i++) ///Sortam perechile de muchii
	{
		sort(Comp_biconexe[i].begin(), Comp_biconexe[i].end());
	}
}
void Componente_biconexe_infoarena()
{
	ifstream f_in("biconex.in");
	ofstream f_out("biconex.out");
	Graf_neorientat graf;
	int Numar_comp_biconexe = 0;
	f_in >> graf;
	vector<vector<pair<int, int>>>Componente_biconexe = graf.Componente_biconexe(Numar_comp_biconexe);
	f_out << Numar_comp_biconexe << '\n';
	Sortare_vector_perechi(Componente_biconexe, Numar_comp_biconexe);///sortam perechile de muchii
	for (int i = 0; i < Numar_comp_biconexe; i++)
	{
		vector<bool>Verifica(graf.get_nr_noduri() + 1, false);
		for (int j = 0; j < Componente_biconexe[i].size(); j++) {
			if (Verifica[Componente_biconexe[i][j].first] == false)
			{
				f_out << Componente_biconexe[i][j].first << " ";
				Verifica[Componente_biconexe[i][j].first] = true;
			}
			if (Verifica[Componente_biconexe[i][j].second] == false)
			{
				f_out << Componente_biconexe[i][j].second << " ";
				Verifica[Componente_biconexe[i][j].second] = true;
			}
		}
		f_out << '\n';
	}

	f_in.close();
	f_out.close();
}

void Sort_topologica_infoarena() {
	ifstream f_in("sortaret.in");
	ofstream f_out("sortaret.out");
	Graf_orientat g;
	f_in >> g;
	vector<int> Rezultat = g.Sortare_topologica();
	for (int i = 0; i < Rezultat.size(); i++)
		f_out << Rezultat[i] << " ";
	f_in.close();
	f_out.close();
}
int main()
{
	///BFS_infoarena();
	///DFS_infoarena();
	Componente_biconexe_infoarena();
	///Sort_topologica_infoarena();

	return 0;
}