#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

class Disjoint_set
{
	int noduri;
	vector<int>tata; // vector in care sunt stocati reprezentantii componentelor/arborilor(reprezentantul arborelui este radacina sa)
	vector<int>h; // vector in care este stocata inaltimea arborilor

public:
	Disjoint_set(int n);
	void initializare(); // initializarea vectorului de tati/reprezentanti + initializarea vectorului de inaltimi
	int reprezentant(int varf); // determinarea radacinii arborelui care contine varf
	void reuneste(int varf1, int varf2); // reuniunea componentelor care contin varf1 si varf2
	void solve_paduri_de_multimi_disjuncte(ifstream& f, ofstream& o);
};

Disjoint_set::Disjoint_set(int n)
{
	noduri = n;
}

void Disjoint_set::initializare()
{
	tata.resize(noduri + 1, 0);
	h.resize(noduri + 1, 0);
}

int Disjoint_set::reprezentant(int varf)
{
	while (tata[varf] != 0)
		varf = tata[varf];

	return varf;
}

void Disjoint_set::reuneste(int varf1, int varf2)
{
	int rv1, rv2;

	rv1 = reprezentant(varf1);
	rv2 = reprezentant(varf2);

	if (h[rv1] > h[rv2]) // reuniunea se face in functie de inaltimea arborilor(arborele cu inaltime mai mica devine subarbore al radacinii celuilalt arbore)
		tata[rv2] = rv1;

	else
	{
		tata[rv1] = rv2;
		if (h[rv1] == h[rv2])
			h[rv2] ++;
	}
}

void Disjoint_set::solve_paduri_de_multimi_disjuncte(ifstream& f, ofstream& o)
{
	int nr_operatii;

	f >> nr_operatii;

	initializare();

	for (int i = 0; i < nr_operatii; i++)
	{
		int cod, x, y;

		f >> cod >> x >> y;

		if (cod == 1)
			reuneste(x, y);

		else
		{
			if (reprezentant(x) == reprezentant(y))
				o << "DA" << "\n";
			else
				o << "NU" << "\n";
		}
	}
}

class Graf
{
	int noduri, muchii;

	void bfs_si_distante(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& distanta_minima); // parcurgere in latime + determinarea distantelor celorlalte varfuri fata de un varf de start
	void dfs(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat); // parcurgere in adancime
	void dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat); // parcurgere in adancime + determinarea timpilor de finalizare: momentul cand se termina de vizitat vecinii unui varf x (si toti vecinii/descendentii acestora), iar varful x este eliminat de pe stiva
	void dfs_graf_transpus(int varf, vector<vector<int>>& vecini_transpus, vector<bool>& vizitat_transpus, vector<vector<int>>& componente_tare_conexe, int nr_componenete_tare_conexe); // parcurgere in adancime a grafului transpus + memorarea componentelor tare conexe
	void dfs_componente_biconexe(int varf_fiu, int varf_tata, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& nivel, vector<int>& nivel_minim, stack<int>& s, vector<vector<int>>& de_afisat, int& nr_componente_biconexe); // parcurgere in adancime + determinarea atat a nivelului pe care se afla fiecare nod, cat si a nivelului minim la care se poate ajunge din acesta + componente biconexe
	void dfs_muchii_critice(int varf_fiu, int varf_tata, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& nivel, vector<int>& nivel_minim, vector<pair<int, int>>& de_afisat); // parcurgere in adacime + determinarea atat a nivelului pe care se afla fiecare nod, cat si a nivelului minim la care se poate ajunge din acesta + muchii critice
	bool havel_hakimi(vector<int>& grade); // constructia unui graf cu secventa gradelor data
	void sortare_havel_hakimi(vector<int>& grade);
	void Dijkstra(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q); // determinarea drumurilor minime de sursa unica start (algoritm pentru grafuri orientate cu circuite, dar cu ponderi pozitive) 
	bool Bellman_Ford(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d); // determinarea drumurilor minime de sursa unica start + circuite de cost negativ(algoritm pentru grafuri orientate cu circuite si ponderi reale, care detecteaza existenta circuitelor negative)
	void Floyd_Warshall(vector<vector<int>>& d, vector<vector<int>>& p); // drumuri minime intre toate perechile de varfuri
	void dfs_diametrul_unui_arbore(int varf, int diametru_curent, int& diametru_max, int& varf_diametru_max, vector<vector<int>>& vecini, vector<bool>& vizitat); // parcurgere in adancime + determinarea celei mai indepartate frunze fata de un varf de start
	void ciclu_eulerian(int varf, vector<vector<pair<int, int>>>& vecini, vector<bool>& vizitat, vector<int>& componente_ciclu_eulerian);

public:
	Graf(int n, int m);
	void solve_bfs_distanta_minima(ifstream& f, ofstream& o);
	void solve_componente_conexe(ifstream& f, ofstream& o);
	void solve_sortare_topologica(ifstream& f, ofstream& o);
	void solve_componente_tare_conexe(ifstream& f, ofstream& o);
	void solve_componente_biconexe(ifstream& f, ofstream& o);
	void solve_muchii_critice(ifstream& f, ofstream& o);
	void solve_havel_hakimi(ifstream& f, ofstream& o);
	void solve_arbore_partial_de_cost_minim_Kruskal(ifstream& f, ofstream& o);
	void solve_Dijkstra(ifstream& f, ofstream& o);
	void solve_Bellman_Ford(ifstream& f, ofstream& o);
	void solve_Floyd_Warshall(ifstream& f, ofstream& o);
	void solve_diametrul_unui_arbore(ifstream& f, ofstream& o);
	void solve_ciclu_eulerian(ifstream& f, ofstream& o);
};

Graf::Graf(int n, int m)
{
	noduri = n;
	muchii = m;
}

void Graf::bfs_si_distante(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& distanta_minima)
{
	queue<int>coada; // coada in care salvez varfurile care sunt vizitate si care urmeaza sa fie explorate(adica cercetez vecinii lor)

	vizitat[varf] = 1; // marchez varful curent ca fiind vizitat

	coada.push(varf); // adaug varful curent in coada pentru a-l explora

	while (!coada.empty()) // cat timp mai am noduri de explorat
	{
		varf = coada.front(); // extrag un varf din coada pentru a-l explora

		// cout << varf << " "; 

		coada.pop();

		for (int j = 0; j < vecini[varf].size(); j++) //marchez toate varfurile adiacente cu el si nevizitate anterior, iar apoi le introduc in coada
			if (!vizitat[vecini[varf][j]])
			{
				vizitat[vecini[varf][j]] = 1;

				coada.push(vecini[varf][j]);

				distanta_minima[vecini[varf][j]] = distanta_minima[varf] + 1; // distanta unui varf nou adaugat este distanta varfului care l-a adaugat + 1
			}
	}
}

void Graf::solve_bfs_distanta_minima(ifstream& f, ofstream& o)
{
	int varf_start; // varful din care trebuie sa incepem parcurgerea

	f >> varf_start;

	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate
	vector<int>distanta_minima(noduri + 1, 0); // vector in care sunt stocate distantele fata de varful de start

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);
	}

	//for (int i = 1; i <= noduri; i++) // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
		//sort(vecini[i].begin(), vecini[i].end());

	bfs_si_distante(varf_start, vecini, vizitat, distanta_minima);

	for (int i = 1; i <= noduri; i++)
		if (i != varf_start && distanta_minima[i] == 0)
			o << "-1 ";
		else
			o << distanta_minima[i] << " ";
}

void Graf::dfs(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat)
{
	// cout << varf << " ";

	vizitat[varf] = 1; // marchez varful curent ca fiind vizitat

	for (int j = 0; j < vecini[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent 
		if (!vizitat[vecini[varf][j]])
			dfs(vecini[varf][j], vecini, vizitat);
}

void Graf::solve_componente_conexe(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;

		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}

	//for (int i = 1; i <= noduri; i++) // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
		//sort(vecini[i].begin(), vecini[i].end());

	int componenete_conexe = 0;

	for (int i = 1; i <= noduri; i++) // pentru fiecare varf ramas nevizitat incrementez variabila componente_conexe si apelez functia de parcurgere in adancime
		if (!vizitat[i])
		{
			componenete_conexe += 1;

			dfs(i, vecini, vizitat);
		}

	o << componenete_conexe;
}

void Graf::dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat)
{
	// cout << varf << " ";

	vizitat[varf] = 1; // marchez varful curent ca fiind vizitat

	for (int j = 0; j < vecini[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat[vecini[varf][j]])
			dfs_si_timp_de_finalizare(vecini[varf][j], vecini, vizitat, stiva_rezultat);

	stiva_rezultat.push(varf); // varfurile sunt adaugate pe stiva in ordinea descrecatoare a timpilor de finalizare 
}

void Graf::solve_sortare_topologica(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate
	stack<int>stiva_rezultat; // stiva in care sunt stocate varfurile in ordinea descrecatoare a timpilor de finalizare

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);
	}

	//for (int i = 1; i <= noduri; i++) // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
		//sort(vecini[i].begin(), vecini[i].end());

	for (int i = 1; i <= noduri; i++)
		if (!vizitat[i])
			dfs_si_timp_de_finalizare(i, vecini, vizitat, stiva_rezultat);

	while (stiva_rezultat.size())
	{
		o << stiva_rezultat.top() << " ";
		stiva_rezultat.pop();
	}
}

void Graf::dfs_graf_transpus(int varf, vector<vector<int>>& vecini_transpus, vector<bool>& vizitat_transpus, vector<vector<int>>& componente_tare_conexe, int nr_componenete_tare_conexe)
{
	// cout << varf << " ";

	componente_tare_conexe[nr_componenete_tare_conexe].push_back(varf);

	vizitat_transpus[varf] = 1; // marchez varful curent ca fiind vizitat

	for (int j = 0; j < vecini_transpus[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat_transpus[vecini_transpus[varf][j]])
			dfs_graf_transpus(vecini_transpus[varf][j], vecini_transpus, vizitat_transpus, componente_tare_conexe, nr_componenete_tare_conexe);
}

void Graf::solve_componente_tare_conexe(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate
	stack<int>stiva_rezultat; // stiva in care sunt stocate varfurile in ordinea descrecatoare a timpilor de finalizare
	vector<vector<int>>vecini_transpus(noduri + 1); // liste de adiacenta pentru graful transpus
	vector<bool>vizitat_transpus(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate din graful transpus
	int nr_componenete_tare_conexe = 0;
	vector<vector<int>>componente_tare_conexe(noduri + 1); // stocarea componentelor tare conexe

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);

		vecini_transpus[y].push_back(x);
	}

	//for (int i = 1; i <= noduri; i++)  // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
	//{
		//sort(vecini[i].begin(), vecini[i].end());
		//sort(vecini_transpus[i].begin(), vecini_transpus[i].end());
	//}

	for (int i = 1; i <= noduri; i++) // este parcurs graful si se determina timpii de finalizare 
		if (!vizitat[i])
			dfs_si_timp_de_finalizare(i, vecini, vizitat, stiva_rezultat);

	while (stiva_rezultat.size()) // graful transpus este parcurs in functie de timpii de finalirizare determinati mai sus
	{
		if (!vizitat_transpus[stiva_rezultat.top()])
		{
			nr_componenete_tare_conexe++;
			dfs_graf_transpus(stiva_rezultat.top(), vecini_transpus, vizitat_transpus, componente_tare_conexe, nr_componenete_tare_conexe);
		}

		stiva_rezultat.pop();
	}

	o << nr_componenete_tare_conexe << "\n";

	for (int i = 1; i <= noduri; i++)
	{
		if (componente_tare_conexe[i].size())
		{
			for (int j = 0; j < componente_tare_conexe[i].size(); j++)
				o << componente_tare_conexe[i][j] << " ";
			o << "\n";
		}
	}
}

void Graf::dfs_componente_biconexe(int varf_fiu, int varf_tata, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& nivel, vector<int>& nivel_minim, stack<int>& s, vector<vector<int>>& de_afisat, int& nr_componente_biconexe)
{
	vizitat[varf_fiu] = 1; // marchez varful fiu ca fiind vizitat
	
	nivel[varf_fiu] = nivel[varf_tata] + 1;  // calculez nivelul pe care se afla fiul

	nivel_minim[varf_fiu] = nivel[varf_fiu]; // initial nivelul minim pe care putem ajunge dintr-un varf este chiar nivelul sau
	
	s.push(varf_fiu);

	for (int j = 0; j < vecini[varf_fiu].size(); j++) 
	{
		if (vecini[varf_fiu][j] != varf_tata) // daca am gasit un varf adiacent cu varful fiu care a fost deja vizitat si nu este tatal sau => muchie de intoarcere
		{
			if (vizitat[vecini[varf_fiu][j]]) // am gasit o muchie de intoarcere, deci verificam daca este cazul sa actualizam nivelul minim la care putem ajunge din varful fiu
			{
				if (nivel_minim[varf_fiu] > nivel[vecini[varf_fiu][j]])
					nivel_minim[varf_fiu] = nivel[vecini[varf_fiu][j]];
			}

			else // daca nu a fost vizitat => DFS din el
			{		
				dfs_componente_biconexe(vecini[varf_fiu][j], varf_fiu, vecini, vizitat, nivel, nivel_minim, s, de_afisat, nr_componente_biconexe);
				
				if (nivel_minim[varf_fiu] > nivel_minim[vecini[varf_fiu][j]]) // verificam daca la revenirea din apel nivelul minim al fiului varfului fiu este mai mic decat al acestuia
					nivel_minim[varf_fiu] = nivel_minim[vecini[varf_fiu][j]];
				
				if (nivel[varf_fiu] <= nivel_minim[vecini[varf_fiu][j]]) // am gasit un nod critic (un nod al carui nivel minim este mai mare sau egal decat nivelul tatalui sau) 
				{	
					while (s.top() != vecini[varf_fiu][j])
					{
						//cout << s.top() << " ";
						de_afisat[nr_componente_biconexe].push_back(s.top());
						s.pop();
					}
					//cout << varf_fiu << " " << "c:" << indice_componenta_biconexa;
					//cout << "\n";
					de_afisat[nr_componente_biconexe].push_back(vecini[varf_fiu][j]);
					s.pop();
					de_afisat[nr_componente_biconexe++].push_back(varf_fiu);
				}
			}
		}
	}
}

void Graf::solve_componente_biconexe(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate
	vector<int>nivel(noduri + 1, 0); // vector in care este stocat nivelul pe care se afla fiecare varf
	vector<int>nivel_minim(noduri + 1, 0); // vector in care este stocat nivelul minim la care se poate ajunge, plecand din fiecare nod x (o sa mergem doar pe muchii ce apartin arborelui DFS si folosim ca ultima muchie o muchie de intoarecere) 
	stack<int>s; // stiva in care varfurile sunt adaugate la vizitare conform parcurgerii si sunt eliminate la determinarea unei componente biconexe
	vector<vector<int>>de_afisat(noduri + 1); // stocarea componentelor biconexe
	int nr_componente_biconexe = 0; 

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;

		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}

	//for (int i = 1; i <= noduri; i++)  // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
		//sort(vecini[i].begin(), vecini[i].end());

	for (int i = 1; i <= noduri; i++)
		if (nivel[i] == 0)
			dfs_componente_biconexe(i, 0, vecini, vizitat, nivel, nivel_minim, s, de_afisat, nr_componente_biconexe);

	o << nr_componente_biconexe << "\n";

	for (int i = 0; i < nr_componente_biconexe; i++)
	{
		for (int j = 0; j < de_afisat[i].size(); j ++)
			o << de_afisat[i][j] << " ";
		o << "\n";
	}
}

void Graf::dfs_muchii_critice(int varf_fiu, int varf_tata, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& nivel, vector<int>& nivel_minim, vector<pair<int, int>>& de_afisat)
{
	vizitat[varf_fiu] = 1; // marchez varful fiu ca fiind vizitat

	nivel[varf_fiu] = nivel[varf_tata] + 1;  // calculez nivelul pe care se afla fiul
	nivel_minim[varf_fiu] = nivel[varf_fiu]; // initial nivelul minim pe care putem ajunge dintr-un varf este chiar nivelul sau

	for (int j = 0; j < vecini[varf_fiu].size(); j++)
	{
		if (vecini[varf_fiu][j] != varf_tata) // daca am gasit un varf adiacent cu varful fiu care a fost deja vizitat si nu este tatal sau => muchie de intoarcere
		{
			if (vizitat[vecini[varf_fiu][j]]) // am gasit o muchie de intoarcere, deci verificam daca este cazul sa actualizam nivelul minim la care putem ajunge din varful fiu
			{
				if (nivel_minim[varf_fiu] > nivel[vecini[varf_fiu][j]])
					nivel_minim[varf_fiu] = nivel[vecini[varf_fiu][j]];
			}

			else // daca nu a fost vizitat => DFS din el
			{
				dfs_muchii_critice(vecini[varf_fiu][j], varf_fiu, vecini, vizitat, nivel, nivel_minim, de_afisat);

				if (nivel_minim[varf_fiu] > nivel_minim[vecini[varf_fiu][j]]) // verificam daca la revenirea din apel nivelul minim al fiului varfului fiu este mai mic decat al acestuia
					nivel_minim[varf_fiu] = nivel_minim[vecini[varf_fiu][j]];

				if (nivel[varf_fiu] < nivel_minim[vecini[varf_fiu][j]]) // determinarea unei muchii critice
					de_afisat.push_back(make_pair(varf_fiu, vecini[varf_fiu][j]));
			}
		}
	}
}

void Graf::solve_muchii_critice(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt marcate varfurile vizitate
	vector<int>nivel(noduri + 1, 0); // vector in care este stocat nivelul pe care se afla fiecare varf
	vector<int>nivel_minim(noduri + 1, 0); // vector in care este stocat nivelul minim la care se poate ajunge, plecand din fiecare nod x(o sa mergem doar pe muchii ce apartin arborelui DFS si folosim ca ultima muchie o muchie de intoarecere)                                          //ultima muchie o muchie de intoarcere)
	vector<pair<int,int>>de_afisat; // vector folosit pentru stocarea muchiilor critice

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;

		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}

	//for (int i = 1; i <= noduri; i++)  // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
		//sort(vecini[i].begin(), vecini[i].end());

	for (int i = 1; i <= noduri; i++)
		if (nivel[i] == 0)
			dfs_muchii_critice(i, 0, vecini, vizitat, nivel, nivel_minim, de_afisat);

	o << de_afisat.size() << "\n";

	for (int i = 0; i < de_afisat.size(); i++)
		o << de_afisat[i].first << " " << de_afisat[i].second << "\n";	
}

bool Graf::havel_hakimi(vector<int>& grade)
{
	sortare_havel_hakimi(grade); // sortez descrecator secventa gradelor

	while (grade[1]) // cat timp mai sunt valori != 0 in secventa 
	{
		int grad_maxim = grade[1]; // selectez cel mai mare numar din secventa gradelor
		grade[1] = 0; // "elimin" cel mai mare numar din secventa gradelor

		for (int i = 2; i <= grad_maxim + 1; i++) // selectez cele mai mari grad_maxim numere din secventa gradelor
		{
			grade[i] --;

			if (grade[i] < 0)
				return 0;
		}

		sortare_havel_hakimi(grade);
	}

	return 1;
}

void Graf::sortare_havel_hakimi(vector<int>& grade)
{
	vector<int>frecvente(noduri, 0);
	int k = 1;

	for (int i = 0; i < noduri; i++)
		frecvente[grade[i + 1]]++;

	for(int i = noduri - 1; i >= 0; i--)
		if (frecvente[i])
		{
			while (frecvente[i])
			{
				grade[k++] = i;
				frecvente[i]--;
			}
		}
}

void Graf::solve_havel_hakimi(ifstream& f, ofstream& o)
{
	vector<int>grade(noduri + 1); // vector in care este salvata secventa gradelor
	int suma = 0; // suma gradelor
	int ok = 1;

	for (int i = 1; i <= noduri; i++)
	{
		f >> grade[i];

		suma += grade[i];

		if (grade[i] >= noduri) // gradul fiecarui varf trebuie sa fie mai mic strict decat numarul de varfuri(conditie necesara, dar nu si suficienta)
		{
			ok = 0;
			o << "NU";
			break;
		}
	}

	if (ok)
	{
		if (suma % 2) // suma gradelor trebuie sa fie un numar par(conditie necesara, dar nu si suficienta)
		{
			ok = 0;
			o << "NU";

		}

		if (ok) // cele doua conditii necesare au fost satisfacute => incercam sa construim graful
		{
			if (havel_hakimi(grade))
				o << "DA";
			else
				o << "NU";
		}
	}
}

void Graf::solve_arbore_partial_de_cost_minim_Kruskal(ifstream& f, ofstream& o)
{
	struct muchie // structura folosita pentru a stoca inf despre o muchie: extremitatile si costul ei
	{
		int x, y, cost;

		bool operator <(const muchie& b)
		{
			return cost < b.cost;
		}
	};

	vector<muchie>v_muchii(muchii); // vector in care sunt stocate muchiile si costul lor
	int cost_arbore = 0;
	int nr_muchii = 0;
	vector<pair<int, int>>de_afisat; // vector in care sunt stocate extremitatile muchiilor ce alcatuiesc arborele partial de cost minim

	for (int i = 0; i < muchii; i++)
		f >> v_muchii[i].x >> v_muchii[i].y >> v_muchii[i].cost;

	sort(v_muchii.begin(), v_muchii.end()); // sortez crescator muchiile dupa cost

	Disjoint_set d(noduri);

	d.initializare();

	for (int i = 0; i < muchii; i++)
	{
		int repr_x = d.reprezentant(v_muchii[i].x);
		int repr_y = d.reprezentant(v_muchii[i].y);

		if (repr_x != repr_y)
		{
			cost_arbore += v_muchii[i].cost;

			de_afisat.push_back(make_pair(v_muchii[i].x, v_muchii[i].y));

			d.reuneste(v_muchii[i].x, v_muchii[i].y);

			nr_muchii += 1;

			if (nr_muchii == noduri - 1)
				break;

		}
	}

	o << cost_arbore << "\n";
	o << nr_muchii << "\n";

	for (auto i : de_afisat)
		o << i.first << " " << i.second << "\n";
}

void Graf::Dijkstra(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q)
{
	d[start] = 0;

	for (int i = 1; i <= noduri; i++)
		q.push(make_pair(d[i], i));

	while (!q.empty())
	{
		int u = q.top().second; // extragem varful cu eticheta minima din q
		q.pop();

		for (auto i = vecini[u].begin(); i != vecini[u].end(); i++) // pentru fiecare muchie uv din E => relaxare
		{
			int v = i->first;
			int lungime = i->second;

			if (d[v] > (d[u] + lungime))
			{
				d[v] = d[u] + lungime; // actualizam lungimea pana la v
				q.push(make_pair(d[v], v));
			}
		}
	}
}

void Graf::solve_Dijkstra(ifstream& f, ofstream& o)
{
	vector<vector<pair<int, int>>>vecini(noduri + 1); //liste de adiacenta in care stochez si lungimea
	vector<int>d((noduri + 1, 1000000)); // vector in care este stocat costul minim al unui drum de la u la v, descoperit pana la acel moment
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; // coada de prioritati in care salvez nodurile neselectate inca

	for (int i = 0; i < muchii; i++)
	{
		int x, y, cost;

		f >> x >> y >> cost;

		vecini[x].push_back(make_pair(y, cost));
	}

	Dijkstra(1, vecini, d, q);

	for (int i = 2; i <= noduri; i++)
		if (d[i] == 1000000)
			o << 0 << " ";
		else
			o << d[i] << " ";
}

bool Graf::Bellman_Ford(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d)
{
	queue<int>q; // coada pentru varfurile ale caror eticheta s-a actualizat
	vector<bool>in_q(noduri + 1, 0);
	vector<int>contor(noduri + 1, 0); // verificam de cate ori a fost relaxat un varf

	d[start] = 0;
	q.push(start);
	in_q[start] = 1;

	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		in_q[u] = 0;

		for (auto i = vecini[u].begin(); i != vecini[u].end(); i++)
		{
			int v = i->first;
			int cost = i->second;

			if (d[v] > d[u] + cost)
			{
				d[v] = d[u] + cost;

				if (in_q[v] == 0)
				{
					q.push(v);
					in_q[v] = 1;
					contor[v]++;
					if (contor[v] > noduri) // am gasit un ciclu negativ
						return 0; 
				}
			}
		}
	}
	
	return 1;
}

void Graf::solve_Bellman_Ford(ifstream& f, ofstream& o)
{
	vector<vector<pair<int, int>>>vecini(noduri + 1); //liste de adiacenta in care stochez si costul
	vector<int>d(noduri + 1, 1000000); // vector in care este stocat costul minim al unui drum de la u la v, descoperit pana la acel moment

	for (int i = 0; i < muchii; i++)
	{
		int x, y, cost;

		f >> x >> y >> cost;

		vecini[x].push_back(make_pair(y, cost));
	}

	if (Bellman_Ford(1, vecini, d))
		for (int i = 2; i <= noduri; i++)
			o << d[i] << " ";
	else
		o << "Ciclu negativ!";
}

void Graf::Floyd_Warshall(vector<vector<int>>& d, vector<vector<int>>& p)
{
	for (int i = 1; i <= noduri; i++)
		for (int j = 1; j <= noduri; j++)
			if (i != j && d[i][j] == 0)
			{
				d[i][j] = 1000000;
				p[i][j] = 0;
			}
			else
				p[i][j] = i;

	for (int k = 1; k <= noduri; k++)
		for (int i = 1; i <= noduri; i++)
			for (int j = 1; j <= noduri; j++)
				if (d[i][j] > d[i][k] + d[k][j])
				{
					d[i][j] = d[i][k] + d[k][j];
					p[i][j] = p[k][j];
				}

	for (int i = 1; i <= noduri; i++)
		for (int j = 1; j <= noduri; j++)
			if (d[i][j] == 1000000 || i == j)
				d[i][j] = 0;
}

void Graf::solve_Floyd_Warshall(ifstream& f, ofstream& o)
{
	vector<vector<int>>d(noduri + 1, vector<int>(noduri + 1)); // matricea distantelor
	vector<vector<int>>p(noduri + 1, vector<int>(noduri + 1)); // predecesor
	
	for (int i = 1; i <= noduri; i++)
		for(int j = 1; j <= noduri; j++)
			f >> d[i][j];
		
	Floyd_Warshall(d, p);

	for (int i = 1; i <= noduri; i++)
	{
		for (int j = 1; j <= noduri; j++)
			o << d[i][j] << " ";
		o << "\n";
	}
}

void Graf::dfs_diametrul_unui_arbore(int varf, int diametru_curent, int& diametru_maxim, int& varf_diametru_max, vector<vector<int>>& vecini, vector<bool>& vizitat)
{
	vizitat[varf] = 1; // marchez varful curent ca fiind vizitat

	if (diametru_curent > diametru_maxim) // actualizez nivelul maxim si varful de pe acest nivel daca este cazul
	{
		diametru_maxim = diametru_curent;
		varf_diametru_max = varf;
	}

	for (int j = 0; j < vecini[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat[vecini[varf][j]])
			dfs_diametrul_unui_arbore(vecini[varf][j], diametru_curent + 1, diametru_maxim, varf_diametru_max, vecini, vizitat);
}

void Graf::solve_diametrul_unui_arbore(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care se marcheaza varfurile vizitate
	int diametru_maxim = 0;
	int varf_diametru_max = 0; // cea mai indepartata frunza fata de varful din care am inceput parcurgerea

	for (int i = 0; i < noduri; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;

		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}

	dfs_diametrul_unui_arbore(1, 0, diametru_maxim, varf_diametru_max, vecini, vizitat); // determinam cea mai indepartata frunza fata de un varf oarecare

	for (int i = 1; i <= noduri; i++)
		vizitat[i] = 0;

	dfs_diametrul_unui_arbore(varf_diametru_max, 0, diametru_maxim, varf_diametru_max, vecini, vizitat); // a doua parcurgere o sa porneasca din cea mai indepartata frunza si o sa determine a doua cea mai indepartata frunza
	
	o << diametru_maxim + 1;
}

void Graf::ciclu_eulerian(int varf, vector<vector<pair<int, int>>>& vecini, vector<bool>& vizitat, vector<int>& componente_ciclu_eulerian)
{
	while (!vecini[varf].empty()) // cat timp mai am vecini pentru varful curent => sterg muchiile formate de varful curent si vecinii sai 
	{
		int varf2 = vecini[varf].back().first;
		int indice_muchie = vecini[varf].back().second;
		vecini[varf].pop_back();

		if (!vizitat[indice_muchie])
		{
			vizitat[indice_muchie] = 1;
			ciclu_eulerian(varf2, vecini, vizitat, componente_ciclu_eulerian);
		}

	}
	componente_ciclu_eulerian.push_back(varf);
}

void Graf::solve_ciclu_eulerian(ifstream& f, ofstream& o)
{
	vector<vector<pair<int, int>>>vecini(noduri + 1); // liste de adiacenta in care stochez si indicele muchiei
	vector<bool>vizitat(muchii + 1); // vector in care se marcheaza muchiile vizitate
	vector<int>componente_ciclu_eulerian; // vector in care sunt stocate extremitatile muchiilor ce alcatuiesc ciclul eulerian(acolo unde exista unul)
	int ok = 1;

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;
		
		vecini[x].push_back(make_pair(y, i));
		vecini[y].push_back(make_pair(x,i));
	}
	
	for (int i = 1; i <= noduri; i++) // verific daca exista varfuri de grad impar
		if (vecini[i].size() % 2)
		{
			ok = 0;
			o << -1;
		}

	if (ok)
	{
		ciclu_eulerian(1, vecini, vizitat, componente_ciclu_eulerian);
		for (int i = 0; i < componente_ciclu_eulerian.size() - 1; i++)
			o << componente_ciclu_eulerian[i] << " ";
	}
}

int main()
{
	int problema = 1;
	// Tema1
	if (problema == 1) //BFS - Parcurgere in latime: https://infoarena.ro/problema/bfs
	{
		ifstream f("bfs.in");
		ofstream o("bfs.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_bfs_distanta_minima(f, o);
	}

	else if (problema == 2) // Parcurgere DFS - componente conexe: https://infoarena.ro/problema/dfs
	{
		ifstream f("dfs.in");
		ofstream o("dfs.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_componente_conexe(f, o);
	}

	else if (problema == 3) // Sortare topologica: https://infoarena.ro/problema/sortaret
	{
		ifstream f("sortaret.in");
		ofstream o("sortaret.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_sortare_topologica(f, o);
	}

	else if (problema == 4) // Componente tare conexe: https://infoarena.ro/problema/ctc
	{
		ifstream f("ctc.in");
		ofstream o("ctc.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_componente_tare_conexe(f, o);
	}

	else if (problema == 5) // Componente biconexe: https://infoarena.ro/problema/biconex
	{
		ifstream f("biconex.in");
		ofstream o("biconex.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_componente_biconexe(f, o);
	}

	else if (problema == 6) // Muchii critice: https://leetcode.com/problems/critical-connections-in-a-network/
	{
		ifstream f("muchiicritice.in");
		ofstream o("muchiicritice.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_muchii_critice(f, o);
	}

	else if (problema == 7) // Havel Hakimi 
	{
		ifstream f("havelhakimi.in");
		ofstream o("havelhakimi.out");

		int noduri;

		f >> noduri;

		Graf g(noduri, 0);

		g.solve_havel_hakimi(f, o);
	}
	// Tema2
	else if (problema == 8) // Paduri de multimi disjuncte: https://infoarena.ro/problema/disjoint
	{
		ifstream f("disjoint.in");
		ofstream o("disjoint.out");

		int noduri;

		f >> noduri;

		Disjoint_set g(noduri);

		g.solve_paduri_de_multimi_disjuncte(f, o);
	}

	else if (problema == 9) // Arbore partial de cost minim: https://infoarena.ro/problema/apm
	{
		ifstream f("apm.in");
		ofstream o("apm.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_arbore_partial_de_cost_minim_Kruskal(f, o);
	}

	else if (problema == 10) // Algoritmul lui Dijkstra: https://infoarena.ro/problema/dijkstra
	{
		ifstream f("dijkstra.in");
		ofstream o("dijkstra.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_Dijkstra(f, o);
	}

	else if (problema == 11) // Algoritmul Bellman-Ford: https://infoarena.ro/problema/bellmanford
	{
		ifstream f("bellmanford.in");
		ofstream o("bellmanford.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_Bellman_Ford(f, o);
	}
	//Tema3
	else if (problema == 12) // Floyd-Warshall/Roy-Floyd: https://infoarena.ro/problema/royfloyd
	{
		ifstream f("royfloyd.in");
		ofstream o("royfloyd.out");

		int noduri;
	
		f >> noduri;

		Graf g(noduri, 0);

		g.solve_Floyd_Warshall(f, o);
	}

	else if (problema == 13) // Diametrul unui arbore: https://infoarena.ro/problema/darb
	{	
		ifstream f("darb.in");
		ofstream o("darb.out");
		
		int noduri;
		
		f >> noduri;

		Graf g(noduri, noduri - 1);

		g.solve_diametrul_unui_arbore(f, o);
	}
	//Tema4
	else if (problema == 14) // Ciclu Eulerian: https://infoarena.ro/problema/ciclueuler
	{
		ifstream f("ciclueuler.in");
		ofstream o("ciclueuler.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_ciclu_eulerian(f, o);
	}

	return 0;
}