#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 si a 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 nivelului pe care se afla fiecare nod, dar si a nivelului minim la care se poate ajunge din acesta + componente biconexe
	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
	bool ciclu_eulerian(vector<vector<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_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 de start ca fiind vizitat

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

	while (coada.size()) // 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; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate
	vector<int>distanta_minima; // vector in care stochez distantele fata de varful de start

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);
	distanta_minima.resize(noduri + 1, 0);

	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++)
		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 de start 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; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 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++)
		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 de start 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 in stiva in ordinea descrecatoare a timpilor de finalizare 
}

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

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);

	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++)
		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 de start 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; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate
	stack<int>stiva_rezultat; // stiva in care sunt stocate varfurile in ordinea descrecatoare a timpilor de finalizare
	vector<vector<int>>vecini_transpus; // liste de adiacenta pentru graful transpus
	vector<bool>vizitat_transpus; // vector in care se marcheaza varfurile vizitate din graful transpus
	int nr_componenete_tare_conexe = 0;
	vector<vector<int>>componente_tare_conexe; // stocarea componentelor tare conexe


	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);
	vecini_transpus.resize(noduri + 1);
	vizitat_transpus.resize(noduri + 1);
	componente_tare_conexe.resize(noduri + 1);

	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++)
	{
		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 se marcheaza 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++)
		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::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; // vector in care sunt stocate muchiile si costul lor
	v_muchii.resize(muchii);

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

	int cost_arbore, nr_muchii;

	cost_arbore = 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++)
	{
		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; //liste de adiacenta in care stochez si lungimea

	vecini.resize(noduri + 1);

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

		f >> x >> y >> cost;

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

	vector<int>d; // vector in care este stocat costul minim al unui drum de la start la u, 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

	d.resize(noduri + 1, 1000000);

	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

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

		f >> x >> y >> cost;

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

	vector<int>d(noduri + 1, 1000000); // vector in care este stocat costul minim al unui drum de la start la u, descoperit pana la acel moment

	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 de start 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

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


	int diametru_maxim = 0; 
	int varf_diametru_max = 0; // cea mai indepartata frunza fata de varful din care am inceput parcurgerea

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

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

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

bool Graf::ciclu_eulerian(vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& componente_ciclu_eulerian)
{
	for (int i = 1; i <= noduri; i++) // verific daca avem noduri de grad impar
		if (vecini[i].size() % 2)
			return 0;

	int varf = 1; // cautam primul nod cu grad != 0

	while (varf <= noduri && vecini[varf].size() == 0)
		varf++;
	
	if (varf == noduri + 1) // toate varfurile au gradul 0
		return 1;

	stack<int>st;
	st.push(varf);
	while (st.size())
	{
		varf = st.top();

		if (vecini[varf].size() == 0)
		{
			componente_ciclu_eulerian.push_back(varf);
			st.pop();
		}
		else
		{
			int varf2 = vecini[varf][0];
			vecini[varf].erase(vecini[varf].begin());

			for(int j = 0; j < noduri; j++)
				if (vecini[varf2][j] == varf)
				{
					vecini[varf2].erase(vecini[varf2].begin() + j);
					break;
				}
			st.push(varf2);
		} 

	}
}

void Graf::solve_ciclu_eulerian(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini(noduri + 1); // liste de adiacenta
	vector<bool>vizitat(noduri + 1, 0); // vector in care sunt stocate gradele varfurilor
	vector<int>componente_ciclu_eulerian; // vector in care sunt stocate extremitatile muchiilor ce alcatuiesc ciclul eulerian(acolo unde exista unul)

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

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

int main()
{
	int problema;

	problema = 12;

	if (problema == 1) //BFS - Parcurgere in latime
	{
		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
	{
		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
	{
		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
	{
		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) // Paduri de multimi disjuncte
	{
		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 == 6) // Arbore partial de cost minim
	{
		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 == 7) // Algoritmul lui 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 == 8) // Algoritmul Bellman-Ford
	{
		ifstream f("bellmanford.in");
		ofstream o("bellmanford.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_Bellman_Ford(f, o);

	}

	else if (problema == 9) // Floyd-Warshall/Roy-Floyd
	{
		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 == 10) // Diametrul unui arbore
	{	
		ifstream f("darb.in");
		ofstream o("darb.out");
		
		int noduri;
		
		f >> noduri;

		Graf g(noduri, noduri - 1);

		g.solve_diametrul_unui_arbore(f, o);
	}

	else if (problema == 11) // Componente biconexe
	{
		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 == 12) // Ciclu Eulerian
	{
		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;
}