#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();
	void DFS(int, vector<int>&, stack<int>&);
	void Transpusa();
	void DFS_transpusa(int, vector<int>&, int, vector<vector<int>>&);
	vector<vector<int>> CTC(int&);

};

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 = 0; 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++) {
		cout << endl;
		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&);
	void Afla_muchii_critice(int, vector<int>&, vector<int>&, vector<int>&, vector<int>&, vector<pair<int, int>>&);
	vector<pair<int, int>> AMC();
};

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 = 0; 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]);
}

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 = 0; i < Lista_de_adiacenta.size(); i++) {
		out << i << ":" << endl;
		for (int j = 0; j < Lista_de_adiacenta[i].size(); j++)
			out << Lista_de_adiacenta[i][j] << " ";
		out << endl;
	}
}

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 Graf_neorientat::Afla_muchii_critice(int Nod_start, vector<int>& Vector_vizitati, vector<int>& Timp_curent, vector<int>& Timp_min, vector<int>& Vector_tati,
	vector<pair<int, int>>& Muchii_critice) {
	static int timp_curent = 0;
	Vector_vizitati[Nod_start] = 0;
	Timp_curent[Nod_start] = Timp_min[Nod_start] = ++timp_curent;
	for (int nod_curent : Lista_de_adiacenta[Nod_start]) {///parcurgem vecinii nodului
		if (nod_curent == Vector_tati[Nod_start]) continue;
		if (Vector_vizitati[nod_curent] == -1) {
			Vector_tati[nod_curent] = Nod_start;
			Afla_muchii_critice(nod_curent, Vector_vizitati, Timp_curent, Timp_min, Vector_tati, Muchii_critice);
			Timp_min[Nod_start] = min(Timp_min[Nod_start], Timp_min[nod_curent]);
			if (Timp_min[nod_curent] > Timp_curent[Nod_start])///daca nu e radacina si fiul are gradul de intoarcere >= decat nivelul nodului
			{
				pair<int, int>Muchii;
				Muchii.first = Nod_start;
				Muchii.second = nod_curent;
				Muchii_critice.push_back(Muchii);
			}
		}
		else
			///actualizam distantele minime
			Timp_min[Nod_start] = min(Timp_min[Nod_start], Timp_curent[nod_curent]);
	}
}

vector<pair<int, int>> Graf_neorientat::AMC() {
	vector<pair<int, int>>Muchii_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, -1);

	for (int i = 0; i < Lista_de_adiacenta.size(); i++)
		if (Vector_vizitati[i] == -1)
			Afla_muchii_critice(i, Vector_vizitati, Timp_curent, Timp_min, Vector_tati, Muchii_critice);
	return Muchii_critice;
}
void Graf_orientat::DFS_transpusa(int Nod_start, vector<int>& Vector_vizitati, int Nr_componente_conexe, vector<vector<int>>& Componente_tare_conexe) {
	Vector_vizitati[Nod_start] = 1; ///Marcam nodul de unde incepe dfs-ul ca vizitat
	Componente_tare_conexe[Nr_componente_conexe].push_back(Nod_start);
	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] == 0)
			DFS_transpusa(nod_curent, Vector_vizitati, Nr_componente_conexe,Componente_tare_conexe);
	}


}
void Graf_orientat::DFS(int Nod_start, vector<int>& Vector_vizitati, stack<int>& Stiva) {
	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, Stiva);
	}
	Stiva.push(Nod_start);

}
void Graf_orientat::Transpusa() {
	vector<vector<int>>Lista_de_adiacenta_transpusa(Nr_noduri+1);
	for(int i=1; i<Lista_de_adiacenta.size(); i++)
		for(int j=0; j<Lista_de_adiacenta[i].size(); j++)
		{
			Lista_de_adiacenta_transpusa[Lista_de_adiacenta[i][j]].push_back(i);
		}
	this->Lista_de_adiacenta.clear();
	Lista_de_adiacenta.resize(Nr_noduri + 1);
	for(int i=1;i<Lista_de_adiacenta_transpusa.size();i++)
		for (int j = 0; j < Lista_de_adiacenta_transpusa[i].size(); j++)
			this->Lista_de_adiacenta[i].push_back(Lista_de_adiacenta_transpusa[i][j]);
}
vector<vector<int>> Graf_orientat::CTC(int& Nr_componente_conexe) {
	vector<vector<int>>Componente_tare_conexe(Nr_noduri+1);
	vector<int>Vector_vizitati(Nr_noduri + 1, -1);
	stack<int>Stiva;
	for (int i = 1; i < Lista_de_adiacenta.size(); i++)
	if(Vector_vizitati[i]==-1)
		DFS(i, Vector_vizitati, Stiva);
	Transpusa();
	while (!Stiva.empty())
	{
		int nod_curent = Stiva.top();
		Stiva.pop();
		if (Vector_vizitati[nod_curent] == 0)
		{
			Nr_componente_conexe++;
			DFS_transpusa(nod_curent, Vector_vizitati, Nr_componente_conexe,Componente_tare_conexe);
		}
	}

	return Componente_tare_conexe;
}

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();
}

void Afla_muchii_critice_rezolvare() {
	int Nr_noduri, Nr_muchii, Start_nod, Nod_st, Nod_dr;
	cin >> Nr_noduri;
	cin >> Nr_muchii;
	vector<pair<int, int>>Vector_perechi_muchii;

	for (int i = 0; i < Nr_muchii; i++)
	{
		cin >> Nod_st;
		cin >> Nod_dr;
		pair<int, int>Muchii;
		Muchii.first = Nod_st;
		Muchii.second = Nod_dr;
		Vector_perechi_muchii.push_back(Muchii);
	}
	vector<vector<int>>Lista_de_adiacenta(Nr_noduri + 1);
	for (int i = 0; i < Vector_perechi_muchii.size(); i++)
	{
		Lista_de_adiacenta[Vector_perechi_muchii[i].first].push_back(Vector_perechi_muchii[i].second);
		Lista_de_adiacenta[Vector_perechi_muchii[i].second].push_back(Vector_perechi_muchii[i].first);
	}
	Graf_neorientat graf(Nr_noduri, Nr_muchii, Lista_de_adiacenta);
	vector<pair<int, int>>Muchii_critice = graf.AMC();
	vector<vector<int>>Rezultat;
	for (int i = 0; i < Muchii_critice.size(); i++) {
		vector<int>Vector;
		Vector.push_back(Muchii_critice[i].first);
		Vector.push_back(Muchii_critice[i].second);
		Rezultat.push_back(Vector);
	}
	if (Rezultat.size() != 0)
		cout << "[";
	for (int i = 0; i < Muchii_critice.size(); i++)
	{
		cout << "[" << Muchii_critice[i].first << "," << Muchii_critice[i].second << "]";
		if (i == Muchii_critice.size() - 1)
			cout << "]";
		else
			cout << ",";
	}
}
bool Hvael_Hakimi_algoritm(vector<int>& Secventa_de_grade) {
	bool val = true;

	while (val == true) {
		sort(Secventa_de_grade.begin(), Secventa_de_grade.end(), greater <>());

		if (Secventa_de_grade[0] == 0)
			return true;

		int Grad_curent = Secventa_de_grade[0];
		Secventa_de_grade.erase(Secventa_de_grade.begin() + 0);
		if (Grad_curent > Secventa_de_grade.size())
			return false;


		for (int i = 0; i < Grad_curent; i++)
		{
			Secventa_de_grade[i]--;
			if (Secventa_de_grade[i] < 0)
				return false;

		}
	}
}

void Hvael_Hakimi_rezolvare() {
	int Nr_noduri, nr;
	cout << "Introduceti numarul de noduri: ";
	cin >> Nr_noduri;
	vector<int>Secventa_de_grade;

	for (int i = 0; i < Nr_noduri; i++)
	{
		cin >> nr;
		Secventa_de_grade.push_back(nr);
	}
	if (Hvael_Hakimi_algoritm(Secventa_de_grade) == true)
		cout << "Da, este posibil.";
	else
		cout << "Nu, nu este posibil.";
}
void Sorteaza_muchii(vector<vector<int>>& Componente_tare_conexe) {
	for(int i=1;i< Componente_tare_conexe.size();i++)
		sort(Componente_tare_conexe[i].begin(), Componente_tare_conexe[i].end());
}

void Componente_tare_conexe_infoarena() {
    ifstream f_in("ctc.in");
	ofstream f_out("ctc.out");
	Graf_orientat g;
	f_in >> g;
	int Nr_componente_conexe = 0;
	vector<vector<int>>Componente_tare_conexe = g.CTC(Nr_componente_conexe);
	f_out << Nr_componente_conexe;
	Sorteaza_muchii(Componente_tare_conexe);
	for (int i = 1; i < Componente_tare_conexe.size(); i++)
	{
		f_out << endl;
		for (int j = 0; j < Componente_tare_conexe[i].size(); j++)
			f_out << Componente_tare_conexe[i][j] << " ";
	}
f_in.close();
f_out.close();
}
int main()
{
	///BFS_infoarena();
	///DFS_infoarena();
	///Componente_biconexe_infoarena();
	///Sort_topologica_infoarena();
	///Afla_muchii_critice_rezolvare();
	///Hvael_Hakimi_rezolvare();
	Componente_tare_conexe_infoarena();

	return 0;
}