#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <utility>
//#include <bits/stdc++.h>

using namespace std;

// Clasa pentru graf
class graf {

protected:
	int noduri, muchii;
	vector < vector < int >> adiacenta;

public:
	// Constructor cu matrice de adiacenta data
	graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

	// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
	graf(int noduri, int muchii) : adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

	vector < int > bfs(int);
	int dfs();

};

// Clasa pentru graf neorientat
class graf_neorientat : public graf {
private:
	void dfsBiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
	void dfsCriticalConnections(int tata, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);
	int bfsDarb(int, int&);

public:
	graf_neorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : graf(listaAdiacenta, noduri, muchii) {};
	graf_neorientat(int noduri, int muchii) : graf(noduri, muchii) {};
	friend istream& operator>>(istream&, graf_neorientat&);

	vector < string > biconex();
	vector < vector < int >> criticalConnections();
	int darb();
	bool isEuler();
	vector<int> euler();

};

// Clasa pentru graf orientat
class graf_orientat : public graf {
private:
	void dfsCtc(int, vector < int >&, vector < int >&, stack < int >&, int&, vector < string >&, unordered_set < int >&);
	void dfsSortaret(int, vector < int >&, vector < int >&);

public:
	graf_orientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : graf(listaAdiacenta, noduri, muchii) {};
	graf_orientat(int noduri, int muchii) : graf(noduri, muchii) {};
	friend istream& operator>>(istream&, graf_orientat&);

	vector < string > ctc();
	vector < int > sortaret();
};

// Clasa pentru graf neorientat ponderat
class graf_neorientat_ponderat : public graf_neorientat {
	// Matrice de adianceta care contine si costurile
	vector< vector< pair< int, int >>> adiacentap;
public:
	graf_neorientat_ponderat(vector < vector < pair<int, int> >> listaAdiacenta, int noduri, int muchii) : adiacentap(listaAdiacenta), graf_neorientat(noduri, muchii) {};
	graf_neorientat_ponderat(int noduri, int muchii) : adiacentap(noduri + 1), graf_neorientat(noduri, muchii) {};
	friend istream& operator>>(istream&, graf_neorientat_ponderat&);

	vector< vector< int >> apm(vector< vector< int >>&, ostream&);
	unordered_map<int, int> bellmanford();

};

// Clasa pentru graf orientat ponderat
class graf_orientat_ponderat : public graf_orientat {
	// Matrice de adianceta care contine si costurile
	vector< vector< pair< int, int >>> adiacentap;
public:
	graf_orientat_ponderat(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : graf_orientat(listaAdiacenta, noduri, muchii) {};
	graf_orientat_ponderat(int noduri, int muchii) : adiacentap(noduri + 1), graf_orientat(noduri, muchii) {};
	friend istream& operator>>(istream&, graf_orientat_ponderat&);

	unordered_map<int, int> dijkstra();
	vector<vector<int>> royfloyd(vector<vector<int>>);
	vector<int> hamilton();

};

// Clasa pentru retea
class retea : public graf_orientat {
	// Matrice de adianceta care contine si costurile
	vector< vector< pair< int, int >>> adiacentap;
	vector<vector<int>> cost;
	bool auxbfs(int start, int finish, vector<int>& parents, vector<vector<int>> matrix, vector<vector<int>> cost);
public:
	retea(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : graf_orientat(listaAdiacenta, noduri, muchii) {};
	retea(int noduri, int muchii) : adiacentap(noduri + 1), graf_orientat(noduri, muchii) {};

	friend istream& operator>>(istream&, retea&);

	int maxflow();

};

// Clasa pentru graf bipartit
class graf_bipartit : public graf_neorientat {
	int stanga, dreapta;
	bool bfsCuplaj(vector<int>&, vector<int>&, vector<int>&);
	bool dfsCuplaj(int, vector<int>&, vector<int>&, vector<int>&);
public:
	graf_bipartit(int stanga, int dreapta, int muchii) : stanga(stanga), dreapta(dreapta), graf_neorientat(stanga + dreapta, muchii) {};

	friend istream& operator>>(istream&, graf_bipartit&);

	vector<pair<int, int>> cuplaj();

};

// Citire pentru graf neorientat
istream& operator>>(istream& in, graf_neorientat& g) {
	for (int i = 0; i < g.muchii; i++) {
		int aux1, aux2;
		in >> aux1 >> aux2;
		g.adiacenta[aux1].push_back(aux2);
		g.adiacenta[aux2].push_back(aux1);
	}
	return in;
}

// Citire pentru graf orientat
istream& operator>>(istream& in, graf_orientat& g) {
	for (int i = 0; i < g.muchii; i++) {
		int aux1, aux2;
		in >> aux1 >> aux2;
		g.adiacenta[aux1].push_back(aux2);
	}
	return in;
}

// Citire pentru graf neorientat ponderat
istream& operator>>(istream& in, graf_neorientat_ponderat& g) {
	for (int i = 0; i < g.muchii; i++) {
		int aux1, aux2, aux3;
		in >> aux1 >> aux2 >> aux3;
		g.adiacentap[aux1].push_back(make_pair(aux2, aux3));
		g.adiacentap[aux2].push_back(make_pair(aux1, aux3));
	}
	return in;
}

// Citire pentru graf orientat ponderat
istream& operator>>(istream& in, graf_orientat_ponderat& g) {
	for (int i = 0; i < g.muchii; i++) {
		int aux1, aux2, aux3;
		in >> aux1 >> aux2 >> aux3;
		g.adiacentap[aux1].push_back(make_pair(aux2, aux3));
	}
	return in;
}

// Citire pentru retea
istream& operator>>(istream& in, retea& g) {
	g.cost.resize(g.noduri + 1, vector<int>(g.noduri + 1));
	for (int i = 0; i < g.muchii; i++) {
		int aux1, aux2, aux3;
		in >> aux1 >> aux2 >> aux3;
		g.cost[aux1][aux2] = aux3;
		g.adiacenta[aux1].push_back(aux2);
		g.adiacenta[aux2].push_back(aux1);
	}
	return in;
}

// Citire pentru graf bipartit
istream& operator>>(istream& in, graf_bipartit& g) {
	for (int i = 0; i < g.muchii; i++) {
		int aux1, aux2;
		in >> aux1 >> aux2;
		g.adiacenta[aux1].push_back(aux2);
	}
	return in;
}


// Parcurgerea in latime a unui graf. Pornind de la un nod, se parcurg toti vecinii lui si se adauga intr-un queue. Se noteaza timpul la care se ajunge la fiecare.
vector < int > graf::bfs(int start) {
	vector < int > rasp(noduri + 1, -1);
	vector < int > vis(noduri + 1);
	queue < int > q;
	vis[start] = 1;
	q.push(start);
	rasp[start] = 0;

	// Se baga pe rand in queue toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (int i : adiacenta[curr])
			if (vis[i] == 0) {
				vis[i] = 1;
				q.push(i);
				rasp[i] = rasp[curr] + 1;
			};
	}
	return rasp;
}

// Parcurgerea in inaltime a unui graf. Se va face pe toate componentele conexe ale grafului. Se parcurg toti vecinii nodului de start si se adauga intr-un stack. De cate ori rulam dfs, atatea componente conexe sunt.
int graf::dfs() {
	vector < int > vis(noduri + 1);
	int res = 0;
	stack < int > s;


	// Se baga pe rand in stack toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele. Se simuleaza call stack-ul de la recursivitate de dfs
	for (int i = 1; i <= noduri; i++) {
		if (vis[i] == 0) {
			res++;
			vis[i] = 1;
			s.push(i);
			while (!s.empty()) {
				int curr = s.top();
				s.pop();
				for (int i = adiacenta[curr].size() - 1; i >= 0; i--) {
					int nod = adiacenta[curr][i];
					if (vis[nod] == 0) {
						vis[nod] = 1;
						s.push(nod);
					}
				}
			}
		}
	}
	return res;
}

// Determina componentele biconexe ale unui graf neorientat, si le pune in vectorul 'rasp'.
void graf_neorientat::dfsBiconex(int tata, vector < int >& timp, vector < int >& rev, stack < pair < int, int >>& s, int& timpcurent, vector < string >& rasp) {
	// Tarjan modificat
	timpcurent++;
	timp[tata] = timpcurent;
	rev[tata] = timpcurent;
	int fiuRadacina = 0;

	// Se tin minte timpii de intoarcere respectiv timpul de intalnire al fiecarui nod in arborele de dfs call
	for (int fiu : adiacenta[tata]) {
		if (timp[fiu] == -1) {
			// Se retine cati fii are fiecare nod in arborele de call dfs
			fiuRadacina++;
			// Se parcurge prin dfs fiecare nod, si cand se gaseste un nod nevizitat se adauga muchia intr-un stack
			s.push(make_pair(tata, fiu));
			dfsBiconex(fiu, timp, rev, s, timpcurent, rasp);
			// Timpul de revenire al unei muchii este minimul dintre timpul de revenire curent si timpul de revenire al fiului,
			// pt ca daca fiul are timp de revenire mai mic si tata il va putea accesa
			rev[tata] = min(rev[tata], rev[fiu]);

			if ((timp[tata] != 1 && rev[fiu] >= timp[tata]) || (timp[tata] == 1 && fiuRadacina > 1)) {
				// Se verifica daca un nod e critic, si sunt 2 cazuri. Primul e cand nodul nu e chiar nodul de incepere al dfs, iar timpul de revenire al fiului este mai mare ca tatal.
				// Practic cand nu suntem intr-un ciclu. Al doilea caz este cel discutat la laborator, cand nodul este chiar radacina arborelui, daca are 2 fii atunci e clar nod critic
				pair < int, int > stop = make_pair(tata, fiu);
				unordered_set < int > aux;
				string str = "";

				// Se face afisare cu string
				aux.insert(stop.first);
				aux.insert(stop.second);
				str += to_string(stop.first);
				str += " ";
				str += to_string(stop.second);
				str += " ";
				// Se parcurge stackul de muchii pana cand dam de muchia care leaga fiul de tata.
				// Se face asta pt ca mai intai se va adauga o muchie intre fiu si tata in stack, apoi se va face dfs
				// si se vor detecta componentele biconexe ale descendentilor si se vor adauga in stack muchiile descendentilor, iar cad se va iesi din dfs-ul descendentilor unui nod tata
				// ce vor ramane in stack vor fi chiar muchiile corespunzatoare componentei biconexe, pana la muchia care leaga tatal de fiu
				while (s.top() != stop) {
					int nodcur = s.top().first;
					if (aux.find(nodcur) == aux.end()) {
						str += to_string(nodcur);
						str += " ";
						aux.insert(s.top().first);
					}
					s.pop();
				}
				str += '\n';
				rasp.push_back(str);
				s.pop();
			}
		}
		else {
			// Daca nodul e deja vizitat, atunci am detectat o muchie de intoarcere,
			// si timpul de revenire al tatalui devine minimul dintre timpul actual de revenire (ca poate fi mai mic, cu o alta muchie gasita deja)
			// si timpul de gasire al fiului
			rev[tata] = min(rev[tata], timp[fiu]);
			// Verificam sa nu fie o muchie care sa duca in fata (in arbore) de fapt, pt ca deja a fost analizata mai devreme in dfs
			if (timp[fiu] < timp[tata]) {
				s.push(make_pair(tata, fiu));
			}
		}
	}
}

// Functie pentru a apela dfs-ul de mai multe ori, si a prelucra rezultatul.
vector < string > graf_neorientat::biconex() {
	vector < int > timp(noduri + 1, -1), rev(noduri + 1);
	stack < pair < int, int >> s;
	vector < string > rasp;
	int timpo = 0;

	// Se porneste dfs-ul din toate componentele conexe, si apoi se adauga la raspuns si ce a mai ramas in stack, pt ca si ce ramane va forma o componenta biconexa
	for (int i = 0; i < noduri; i++) {
		if (timp[i] == -1) {
			dfsBiconex(i, timp, rev, s, timpo, rasp);
		}
		if (!s.empty()) {
			unordered_set < int > aux;
			string str;

			while (!s.empty()) {
				if (aux.find(s.top().first) == aux.end()) {
					aux.insert(s.top().first);
					str += to_string(s.top().first);
					str += " ";
				}
				if (aux.find(s.top().second) == aux.end()) {
					aux.insert(s.top().second);
					str += to_string(s.top().second);
					str += " ";
				}
				s.pop();
			}
			str += '\n';
			rasp.push_back(str);
		}
	}
	return rasp;
}

// Functie bfs de ajutor pentru diametrul unui arbore
int graf_neorientat::bfsDarb(int start, int& finish) {
	vector < int > rasp(noduri + 1);
	vector < int > vis(noduri + 1);
	queue < int > q;
	vis[start] = 1;
	q.push(start);
	rasp[start] = 0;

	// Se baga pe rand in queue toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (int i : adiacenta[curr]) {
			if (vis[i] == 0) {
				vis[i] = 1;
				q.push(i);
				rasp[i] = rasp[curr] + 1;
				finish = i;
			}
		}
	}
	return rasp[finish];
}

// Functie care returneaza diametrul unui arbore
int graf_neorientat::darb() {
	int last = 0, aux;
	aux = bfsDarb(1, last);
	aux = bfsDarb(last, last);
	return aux + 1;
}

// Functie care verifica daca un graf neorientat poate fi euler
bool graf_neorientat::isEuler() {
	// Daca orice nod are gradul impar atunci graful nu poate fi eulerian
	for (int i = 1; i < adiacenta.size(); i++) {
		if (adiacenta[i].size() % 2 != 0) {
			return 0;
		}
	}
	return 1;
}

// Functie care returneaza ciclul euler al unui graf eulerian
vector<int> graf_neorientat::euler() {
	// Algoritmul lui Hierholzer
	// Se incepe dintr-un nod oarecare si se parcurge graful cam ca intr-un dfs pana ajungem din nou la nodul de inceput, numai ca stergem muchiile prin care trecem
	// Acest lucru e garantat sa se intample pt ca graful e eulerien
	// Dupa ce am ajuns inapoi, adaugam nodul de start la drumul eulerian final, si ne intoarcem in dfs pentru a gasi un nod care inca are muchii care pot fi accesate
	// si incepem la fel ca inainte cu alt nod
	// Acest lucru se bazeaza pe faptul ca un graf eulerian se poate descompune in cicluri disjuncte

	stack<int> curent;
	vector<int> raspuns;

	// Se incepe cu un nod oarecare, 1 in cazul nostru
	curent.push(1);

	// Cat timp exista noduri in ciclul curent
	while (!curent.empty()) {
		// Se ia primul nod
		int nod = curent.top();

		// Se verifica daca are vecini
		if (adiacenta[nod].size()) {
			// Se ia un vecin si se baga in ciclul curent
			int nod1 = adiacenta[nod].back();
			curent.push(nod1);

			// Se sterge muchia
			adiacenta[nod].pop_back();
			int i;
			for (i = 0; i < adiacenta[nod1].size(); i++) {
				if (adiacenta[nod1][i] == nod) {
					break;
				}
			}
			adiacenta[nod1].erase(adiacenta[nod1].begin() + i);
		}
		else {
			// Daca nodul nu mai are niciun vecin accesibil, de intoarcem la nodul dinaintea lui poate are el
			raspuns.push_back(nod);
			curent.pop();
		}
	}
	return raspuns;
}

// Determina componentele tare conexe ale unui graf orientat, si le pune in 'rasp'.
void graf_orientat::dfsCtc(int tata, vector < int >& timp, vector < int >& rev, stack < int >& s, int& timpcurent, vector < string >& rasp, unordered_set < int >& check) {
	// Tarjan
	timpcurent++;
	timp[tata] = timpcurent;
	rev[tata] = timpcurent;
	s.push(tata);
	check.insert(tata);

	// Se tin minte timpii de intoarcere respectiv timpul de intalnire al fiecarui nod in arborele de dfs call
	for (int fiu : adiacenta[tata]) {
		if (timp[fiu] == -1) {
			// Cand descoperim un fiu nevizitat facem dfs
			dfsCtc(fiu, timp, rev, s, timpcurent, rasp, check);
			// Timpul de revenire al unei muchii este minimul dintre timpul de revenire curent si timpul de revenire al fiului,
			// pt ca daca fiul are timp de revenire mai mic si tata il va putea accesa
			rev[tata] = min(rev[tata], rev[fiu]);
		}
		// Daca nodul e deja vizitat, atunci am detectat o muchie de intoarcere,
		// si timpul de revenire al tatalui devine minimul dintre timpul actual de revenire (ca poate fi mai mic, cu o alta muchie gasita deja)
		// si timpul de gasire al fiului
		else if (check.find(fiu) != check.end()) {
			rev[tata] = min(rev[tata], timp[fiu]);
		}
	}
	// Dupa ce se parcurg toti descendentii tatalui, verificam daca timpul de revenire al tatalui este egal cu timpul de intalnire al sau.
	// Daca sunt egale, exista doua cazuri, ori tatal face parte dintr-o componenta tare conexa cu descendenti de-ai sai bagati deja in stack,
	// ori el este o componenta tare conexa singur.
	// Se vor salva nodurile rezultate in stringuri. Check tine minte daca un element e in stack sau nu, caci daca nu e poate forma o componenta tare conexa cu altcineva
	if (timp[tata] == rev[tata]) {
		string aux = "";
		while (s.top() != tata) {
			aux += to_string(s.top());
			aux += " ";
			check.erase(s.top());
			s.pop();
		}
		aux += to_string(s.top());
		aux += " ";
		check.erase(s.top());
		s.pop();
		aux += '\n';
		rasp.push_back(aux);
	}
}

// Functie pentru a apela dfs-ul de mai multe ori, si a prelucra rezultatul.
vector < string > graf_orientat::ctc() {
	vector < int > timp(noduri + 1, -1), rev(noduri + 1);
	unordered_set < int > check;
	stack < int > s;
	vector < string > rasp;
	int timpo = 0;

	// Se porneste dfs-ul din toate componentele conexe, si apoi se adauga la raspuns si ce a mai ramas in stack, pt ca si ce ramane va forma o componenta biconexa
	for (int i = 1; i <= noduri; i++) {
		if (timp[i] == -1) {
			dfsCtc(i, timp, rev, s, timpo, rasp, check);
		}
	}
	return rasp;
}

// Functie pentru a sorta topologim un graf. Ordinea va fi returnata in vectorul 'res'.
void graf_orientat::dfsSortaret(int tata, vector < int >& vis, vector < int >& res) {
	// Se face dfs cu recursivitate
	for (int fiu : adiacenta[tata]) {
		if (!vis[fiu]) {
			vis[fiu] = 1;
			dfsSortaret(fiu, vis, res);
		}
	}
	// Cand se termina de cautat in fii unui nod, se adauga la raspuns, pt ca inseamna ca nu mai depinde nimeni de el
	res.push_back(tata);
}

// Functie pentru a apela dfs-ul de mai multe ori, si a prelucra rezultatul.
vector < int > graf_orientat::sortaret() {
	vector < int > vis(this->noduri + 1);
	vector < int > res;

	// Se face dfs pt fiecare componenta conexa
	for (int i = 1; i <= this->noduri; i++) {
		if (vis[i] == 0) {
			vis[i] = 1;
			dfsSortaret(i, vis, res);
		}
	}
	return res;
}

// Functie pentru a gasi muchiile critice dintr-un graf, rezultatul va fi pus in rasp.
void graf_neorientat::dfsCriticalConnections(int tata, vector < int >& timp, vector < int >& rev, int& timpcurent, vector < vector < int >>& rasp, vector < int >& parinte) {
	// Tarjan modificat
	timpcurent++;
	timp[tata] = timpcurent;
	rev[tata] = timpcurent;

	// Se tin minte timpii de intoarcere respectiv timpul de intalnire al fiecarui nod in arborele de dfs call
	for (int fiu : adiacenta[tata]) {
		// Tinem minte parintele direct din arborele dfs
		parinte[fiu] = tata;
		if (timp[fiu] == -1) {
			// Cand descoperim un fiu nevizitat facem dfs
			dfsCriticalConnections(fiu, timp, rev, timpcurent, rasp, parinte);
			// Timpul de revenire al unei muchii este minimul dintre timpul de revenire curent si timpul de revenire al fiului,
			// pt ca daca fiul are timp de revenire mai mic si tata il va putea accesa
			rev[tata] = min(rev[tata], rev[fiu]);
			if (rev[fiu] > timp[tata]) {
				vector < int > aux;
				aux.push_back(tata);
				aux.push_back(fiu);
				rasp.push_back(aux);
			}
		}
		// Daca nodul e deja vizitat, atunci am detectat o muchie de intoarcere,
		// si timpul de revenire al tatalui devine minimul dintre timpul actual de revenire (ca poate fi mai mic, cu o alta muchie gasita deja)
		// si timpul de gasire al fiului
		// Se verifica ca muchia sa nu fie una prezenta deja, sa nu fie una care sa mearga in fata in arborele dfs
		else if (parinte[tata] != fiu) {
			rev[tata] = min(rev[tata], timp[fiu]);
		}
	}
}

// Functie pentru a apela dfs-ul de mai multe ori, si a prelucra rezultatul.
vector < vector < int >> graf_neorientat::criticalConnections() {
	vector < int > timp(noduri + 1, -1), rev(noduri + 1), parinte(noduri + 1);
	vector < vector < int >> rasp;
	int timpo = 0;

	// Se face dfs pt fiecare componenta conexa
	for (int i = 1; i <= noduri; i++) {
		if (timp[i] == -1) {
			dfsCriticalConnections(i, timp, rev, timpo, rasp, parinte);
		}
	}
	return rasp;
}

// Functie care primeste un vector care contine gradele nodurilor unui graf, si determina daca se poate forma un graf cu ele sau nu. Este in afara clasei pentru ca nu face operatii pe un graf
bool havelHakimi(vector < int >& a) {
	// Mai intai se sorteaza vectorul ca sa avem mereu nodul cu cel mai mare grad primul
	sort(a.begin(), a.end(), [](int m, int n) {
		return m > n;
		});
	int x = a[0];

	// Daca mai e un singur nod in vector cu grad nenul, evident, nu se va putea face graf cu el
	if (a.size() == 1 && x >= 1) {
		return false;
	}
	// Daca primul nod e 0, tinand cont ca vectorul e sortat crescator, atunci toate sunt 0 si e bine, se poate forma graf
	if (x == 0) {
		return true;
	}

	// Se sterge primul element din vector, ii facem legaturile
	a.erase(a.begin() + 0);

	// Daca nodul are grad mai mare decat sunt legaturi posibile atunci e clar ca nu e posibil sa facem graf
	if (x > a.size()) {
		return false;
	}
	// 'Conectam' primul nod la urmatoarele noduri din vector, cate ne spune gradul lui
	for (int i = 0; i < x; i++) {
		a[i]--;
		// Daca un nod ajunge cu gradul pe minus, e clar ca nu se paote face graf
		if (a[i] < 0) {
			return false;
		}
	}
	// Apelam recursiv cu noul vector format
	return havelHakimi(a);
}

// Functie care creeaza un graf partial de cost minim pornind de la un graf ponderat
vector< vector< int >> graf_neorientat_ponderat::apm(vector< vector< int >>& much, ostream& out) {
	// Kruskal
	// Se vor adauga muchii in ordine crescatoare care sa nu inchida un ciclu in graf
	// Vom realiza asta retinand tatal fiecarui nod din arborii partiali formati pana la un moment dat. Astea vor fi puse in vectorul tata
	vector< int > tata(noduri + 1);
	vector< vector < int >> rasp;

	// Sortam muchiile dupa cost
	sort(much.begin(), much.end(), [](vector<int> a, vector<int> b) {
		return a[2] < b[2];
		});

	int i = 0, j = 0;
	long long s = 0;

	// Initializam vectorul tata, fiecarui nod ii atribuim tata chiar pe el, pentru a ne da seama cand nodul nu are de fapt tata
	for (int i = 1; i < tata.size(); i++) {
		tata[i] = i;
	}

	// Ciclam prin muchii pana cand am adaugat suficiente ca graful sa fie conex
	while (i < this->noduri - 1) {
		// Se iau nodurile care formeaza o muchie
		int nod1 = much[j][0], nod2 = much[j][1];
		int tata1 = nod1, tata2 = nod2;

		// Se gaseste radacina arborilor partiali din care fac parte nodurile
		while (tata1 != tata[tata1]) {
			tata1 = tata[tata1];
		}
		while (tata2 != tata[tata2]) {
			tata2 = tata[tata2];
		}

		// Daca 2 noduri fac parte din arbori diferiti, adica radacinile lor sunt diferite, am gasit o muchie pe care s-o adaugam in arborele partial de cost minim
		if (tata1 != tata2) {
			// Adaugam costul muchiei adaugate la costul final
			s += much[j][2];

			// Unim 2 arbori partiali
			// Unim mereu arborele cu radacina mai mare dpdv lexicografic cu arborele cu radacina mai mica, pentru a-i avea intr-o anumita ordine si pentru a fi sanse mai mari sa se lege arbori
			// Direct de radacina, si deci sa avem inaltimi mai mici ale arborilor
			if (tata[tata1] < tata[tata2]) {
				tata[tata1] = tata[tata2];
			}
			else {
				tata[tata2] = tata[tata1];
			}

			// Adaugam muchia la raspuns
			rasp.push_back({ nod1, nod2 });
			i++;
		}
		j++;
	}

	// Afisare suma si numar muchii din graf
	out << s << '\n' << this->noduri - 1 << '\n';
	return rasp;
}

// Functie care poate face 2 actiuni, uneste 2 paduri sau afiseaza daca 2 noduri sunt in aceeasi padur sau nu
void disjoint(istream& in, ostream& out) {

	int n, m;
	in >> n >> m;

	// Vectorul in care tinem minte tatii, initial tatal lui i va fi chiar i, pt totul e deconectat
	vector< int > tata(n + 1);

	for (int i = 1; i < tata.size(); i++) {
		tata[i] = i;
	}

	// Mergem prin operatii
	for (int i = 0; i < m; i++) {
		int tip, nod1, nod2;
		in >> tip >> nod1 >> nod2;
		int tata1 = nod1, tata2 = nod2;

		// Descoperim care sunt radacinile arborilor nodurilor de care avem nevoie
		while (tata[tata1] != tata1) {
			tata1 = tata[tata1];
		}
		while (tata[tata2] != tata2) {
			tata2 = tata[tata2];
		}

		// Vedem de ce tip e operatia
		if (tip == 1) {
			// Se unesc 2 arbori
			tata[tata1] = tata[tata2];
		}
		else {
			// Daca radacinile celor 2 arbori corespunzatori nodurilor date coincid, e clar ca si arborii coincid
			if (tata1 == tata2) {
				out << "DA\n";
			}
			else {
				out << "NU\n";
			}

			// Dupa ce facem actiunea asta, se face o euristica, si anume unim toate nodurile din arborii tocmai accesati chiar de radacina arborilor in care sunt
			while (tata[nod1] != nod1) {
				tata[nod1] = tata1;
				nod1 = tata[nod1];
			}
			while (tata[nod2] != nod2) {
				tata[nod2] = tata2;
				nod2 = tata[nod2];
			}
		}
	}
}

// Functie care returneaza drumul minim de la nodul 1 la fiecare nod din graf orientat
unordered_map<int, int> graf_orientat_ponderat::dijkstra() {

	// Aici tinem distantele
	unordered_map<int, int> m;
	// Priority queue (heap) pentru a tine minte mereu nodul la care se poate ajunge cel mai rapid
	priority_queue<vector<int>> p;
	// Tinem minte daca nodul a fost deja vizitat
	vector<bool> vis(noduri + 1, false);

	// Stim ca incepem din nodul 1 mereu deci distanta va fi 0, si il adaugam in heap
	m[1] = 0;
	p.push({ 0, 1 });

	// Mergem prin priority queue pana cand nu mai avem ce lua din el
	while (!p.empty()) {
		// Luam cel mai mic nod
		int curNod = p.top()[1];
		p.pop();

		// Daca nodul nu a fost deja analizat, incepem analizarea lui
		if (!vis[curNod]) {
			vis[curNod] = true;

			// Ne uitam la vecinii lui
			for (auto i : adiacentap[curNod]) {
				int nod = i.first, cost = i.second;

				// Daca distanta pana la nod nu a fost inca determinata sau e mai mare decat lungimea calculata acum, o modificam
				if (m.find(nod) == m.end() || m[nod] > m[curNod] + cost) {
					m[nod] = m[curNod] + cost;
					p.push({ -(m[nod]), nod });
				}
			}
		}
	}
	return m;

}

// Functie care returneaza drumul minim de la nodul 1 la fiecare nod din graf neorientat. Merge si pe costuri negative
unordered_map<int, int> graf_neorientat_ponderat::bellmanford() {
	// Map sa tinem minte costul pana la fiecare mod
	unordered_map<int, int> m;
	// Queue pentru a tine minte nodurile care ar putea fi relaxate
	queue<int> q;
	// De cate ori a fost relaxat un nod
	vector<int> cnt(noduri + 1);
	// Daca un nod este in queue sau nu
	unordered_set<int> check;

	// Incepem de la nodul 1
	m[1] = 0;
	q.push(1);
	check.insert(1);

	// Cat timp coada are noduri in ea, parcurgem nodurile din coada
	while (!q.empty()) {
		// Luam nodul din capul cozii
		int nod1 = q.front();
		check.erase(nod1);
		q.pop();

		// Parcurgem lista de adiacenta a nodului pe care l-am luat
		for (pair<int, int> muchie : adiacentap[nod1]) {
			// Retinem nodurile si costurile la care duc muchiile din nod
			int nod2 = muchie.first, cost = muchie.second;

			// Daca un nod nu are cost sau costul pe care il avem deja e mai mare decat costul pe care l-am forma cu noua muchie gasita, facem update
			if (m.find(nod2) == m.end() || m[nod2] > m[nod1] + cost) {
				// Updatam costul
				m[nod2] = m[nod1] + cost;

				// Daca al doilea nod nu este in queue, il bagam, pt ca stim ca exista posibiltatea ca vecinii lui sa poata fi relaxati
				if (check.find(nod2) == check.end()) {
					q.push(nod2);
					check.insert(nod2);
					cnt[nod2]++;

					// Daca un nod a fost relaxat de mai multe ori decat sunt noduri, e clar ca exista un ciclu care reduce mereu costul
					if (cnt[nod2] > noduri) {
						// Returnam un map gol pentru a semnala acest lucru
						m.clear();
						return m;
					}
				}
			}
		}
	}
	return m;
}

// Functie ajutatoare bfs pentru maxflow
bool retea::auxbfs(int start, int finish, vector<int>& parents, vector<vector<int>> matrix, vector<vector<int>> cost) {
	vector < int > vis(noduri + 1);
	queue < int > q;
	q.push(start);
	vis[1] = 1;

	// Se baga pe rand in queue toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele
	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		for (int i : adiacenta[curr]) {
			if (!vis[i] && cost[curr][i] > matrix[curr][i]) {
				parents[i] = curr;
				q.push(i);
				vis[i] = 1;
			}
		}
	}
	return vis[noduri];
}

// Functie care primeste o retea si returneaza fluxul maxim care poate fi transmis de la sursa la desinatie prin retea
int retea::maxflow() {
	vector<int> parents(noduri + 1);
	vector<vector<int>> matrix(noduri + 1, vector<int>(noduri + 1));

	int m = 0, start = 1, finish = noduri, currm = INT_MAX;

	while (this->auxbfs(start, finish, parents, matrix, cost)) {
		for (auto p : adiacenta[noduri]) {
			if (cost[p][noduri] > matrix[p][noduri]) {
				parents[noduri] = p;
				currm = cost[p][finish] - matrix[p][finish];
				int j;
				for (int i = p; i != 1; i = parents[i]) {
					j = parents[i];
					currm = min(currm, cost[j][i] - matrix[j][i]);
				}
				matrix[p][finish] += currm;
				matrix[finish][p] -= currm;
				for (int i = p; i != 1; i = parents[i]) {
					j = parents[i];
					matrix[j][i] += currm;
					matrix[i][j] -= currm;
				}
				m += currm;
			}
		}
	}
	return m;
}

// Functie care returneaza pornind de la matricea de adiacenta cu costuri cel mai scurt drum de la fiecare nod la fiecare nod
vector<vector<int>> graf_orientat_ponderat::royfloyd(vector<vector<int>> rasp) {
	// Incearca sa gaseasca pentru fiecare 2 noduri i si j, un nod k prin care daca trecem sa devina costul de la i la j mai mic
	for (int k = 1; k <= noduri; k++) {
		for (int i = 1; i <= noduri; i++) {
			for (int j = 1; j <= noduri; j++) {
				// Verificam conditia enuntata mai sus. Avem grija ca i si j sa fie accesibile din k iar i si j sa nu fie chiar acelasi nod
				if ((rasp[i][k] + rasp[k][j] < rasp[i][j] || rasp[i][j] == 0) && rasp[k][j] && rasp[i][k] && i != j) {
					rasp[i][j] = rasp[i][k] + rasp[k][j];
				}
			}
		}
	}

	return rasp;
}

vector<int> graf_orientat_ponderat::hamilton()
{
	return { 0 };
}

bool graf_bipartit::bfsCuplaj(vector<int>& pereche_stanga, vector<int>& pereche_dreapta, vector<int>& distanta) {
	queue<int> q;

	for (int nod = 1; nod <= stanga; nod++) {
		if (!pereche_stanga[nod]) {
			q.push(nod);
			distanta[nod] = 0;
		}
		else {
			distanta[nod] = INT_MAX;
		}
	}

	distanta[0] = INT_MAX;

	while (!q.empty()) {
		int nod1 = q.front();
		q.pop();
		if (distanta[nod1] < distanta[0]) {
			for (int nod2 : adiacenta[nod1]) {
				if (distanta[pereche_dreapta[nod2]] == INT_MAX) {
					distanta[pereche_dreapta[nod2]] = distanta[nod1] + 1;
					q.push(pereche_dreapta[nod2]);
				}
			}
		}
	}

	return (distanta[0] != INT_MAX);
}

bool graf_bipartit::dfsCuplaj(int start, vector<int>& pereche_stanga, vector<int>& pereche_dreapta, vector<int>& distanta) {
	if (!start) {
		return true;
	}
	for (int nod : adiacenta[start]) {
		if (distanta[pereche_dreapta[nod]] == distanta[start] + 1) {
			if (dfsCuplaj(pereche_dreapta[nod], pereche_stanga, pereche_dreapta, distanta)) {
				pereche_dreapta[nod] = start;
				pereche_stanga[start] = nod;
				return true;
			}
		}
	}
	distanta[start] = INT_MAX;
	return false;
}

vector<pair<int, int>> graf_bipartit::cuplaj()
{
	vector<int> pereche_stanga(stanga + 1);
	vector<int> pereche_dreapta(dreapta + 1);
	vector<int> distanta(stanga + 1);

	int raspuns = 0;
	while (bfsCuplaj(pereche_stanga, pereche_dreapta, distanta)) {
		for (int i = 1; i <= stanga; i++) {
			if (!pereche_stanga[i] && dfsCuplaj(i, pereche_stanga, pereche_dreapta, distanta)) {
				raspuns++;
			}
		}
	}
	vector<pair<int, int>> r;
	r.push_back(make_pair(raspuns, raspuns));
	return r;
}

// Functii in care se face citirea si afisarea specifica fiecarei probleme,
void bfsDriver() {
	// https://infoarena.ro/problema/bfs
	// Citire
	ifstream in("bfs.in");
	ofstream out("bfs.out");

	int n, m, s; in >> n >> m >> s;
	graf_orientat x(n, m);

	in >> x;

	// Afisare
	vector < int > rasp = x.bfs(s);
	for (int i = 1; i <= n; i++) {
		out << rasp[i] << " ";
	}

	in.close();
	out.close();
}

void dfsDriver() {
	// https://infoarena.ro/problema/dfs
	// Citire
	ifstream in("dfs.in");
	ofstream out("dfs.out");

	int n, m; in >> n >> m;
	graf_neorientat x(n, m);

	in >> x;

	// Afisare
	out << x.dfs();

	in.close();
	out.close();
}

void biconexDriver() {
	// https://infoarena.ro/problema/biconex
	// Citire
	ifstream in("biconex.in");
	ofstream out("biconex.out");

	int n, m; in >> n >> m;
	graf_neorientat x(n, m);

	in >> x;

	// Afisare
	vector < string > fin = x.biconex();
	out << fin.size() << '\n';
	for (string i : fin) {
		out << i;
	}

	in.close();
	out.close();
}

void ctcDriver() {
	// https://infoarena.ro/problema/ctc
	// Citire
	ifstream in("ctc.in");
	ofstream out("ctc.out");

	int n, m; in >> n >> m;
	graf_orientat x(n, m);

	in >> x;

	// Afisare
	vector < string > fin = x.ctc();
	out << fin.size() << '\n';
	for (string i : fin) {
		out << i;
	}

	in.close();
	out.close();
}

void sortaretDriver() {
	// https://infoarena.ro/problema/sortaret
	// Citire
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");

	int n, m; in >> n >> m;
	graf_orientat x(n, m);

	in >> x;

	// Afisare
	// Citim vectorul invers fata de cum l-am creat, pt ca ultimul nod care e accesat e nodul cu cele mai multe dependente
	vector < int > res = x.sortaret();
	for (int i = res.size() - 1; i >= 0; i--) {
		out << res[i] << " ";
	}

	in.close();
	out.close();
}

void havelHakimiDriver() {
	// Citire
	ifstream in("havelhakimi.in");
	ofstream out("havelhakimi.out");

	int n; in >> n;
	vector < int > a;

	// Afisare
	for (int i = 0; i < n; i++) {
		int aux; in >> aux;
		a.push_back(aux);
	}
	out << havelHakimi(a);

	in.close();
	out.close();
}

void criticalConnectionsDriver() {
	// https://leetcode.com/problems/critical-connections-in-a-network/
	// Citire
	int n, m;
	cin >> n >> m;
	graf_neorientat x(n, m);

	cin >> x;

	// Afisare
	vector < vector < int >> fin = x.criticalConnections();
	for (auto i : fin) {
		for (auto j : i) {
			cout << j << " ";
		}
	}
}

void apmDriver() {
	// https://infoarena.ro/problema/apm
	// Citire
	ifstream in("apm.in");
	ofstream out("apm.out");

	int n, m;
	in >> n >> m;
	graf_neorientat_ponderat x(n, m);
	vector< vector< int >> much;
	for (int i = 0; i < m; i++) {
		int aux1, aux2, aux3;
		in >> aux1 >> aux2 >> aux3;
		much.push_back({ aux1, aux2, aux3 });
	}

	// Afisare
	vector< vector< int >> v = x.apm(much, out);
	for (auto i : v) {
		out << i[0] << " " << i[1] << "\n";
	}

}

void disjointDriver() {
	// // https://infoarena.ro/problema/disjoint
	// Citire
	ifstream in("disjoint.in");
	ofstream out("disjoint.out");

	// Apelare
	disjoint(in, out);

}

void dijkstraDriver() {
	// https://infoarena.ro/problema/dijkstra
	// Citire
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");

	int n, m;
	in >> n >> m;

	graf_orientat_ponderat x(n, m);
	in >> x;

	// Afisare
	unordered_map<int, int> v = x.dijkstra();
	for (int i = 2; i <= n; i++) {
		if (v.find(i) == v.end()) {
			out << "0 ";
		}
		else {
			out << v[i] << " ";
		}
	}
}

void bellmanfordDriver() {
	// https://infoarena.ro/problema/bellmanford
	// Citire
	ifstream in("bellmanford.in");
	ofstream out("bellmanford.out");

	int n, m;
	in >> n >> m;

	vector<vector<pair<int, int>>> muchii(n + 1);
	for (int i = 0; i < m; i++) {
		int aux1, aux2, aux3;
		in >> aux1 >> aux2 >> aux3;
		muchii[aux1].push_back(make_pair(aux2, aux3));
	}

	graf_neorientat_ponderat x(muchii, n, m);

	// Afisare
	unordered_map<int, int> v = x.bellmanford();
	if (v.empty()) {
		out << "Ciclu negativ!";
	}
	else {
		for (int i = 2; i <= n; i++) {
			out << v[i] << " ";
		}
	}

}

void maxflowDriver() {
	// https://infoarena.ro/problema/maxflow
	// Citire
	ifstream in("maxflow.in");
	ofstream out("maxflow.out");

	int n, m;
	in >> n >> m;

	retea x(n, m);
	in >> x;

	// Afisare
	out << x.maxflow();

}

void royfloydDriver() {
	// https://infoarena.ro/problema/royfloyd
	// Citire
	ifstream in("royfloyd.in");
	ofstream out("royfloyd.out");

	int n, m = 0;
	in >> n;

	vector<vector<int>> matrix(n + 1, vector<int>(n + 1));

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			in >> matrix[i][j];
		}
	}

	graf_orientat_ponderat x(n, m);

	// Afisare
	vector<vector<int>> rasp = x.royfloyd(matrix);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			out << rasp[i][j] << " ";
		}
		out << '\n';
	}
}

void darbDriver() {
	// https://infoarena.ro/problema/darb
	// Citire
	ifstream in("darb.in");
	ofstream out("darb.out");

	int n, m = 0, a, b;
	in >> n;
	vector < vector < int >> listaAdiacenta(n + 1);

	while (in >> a >> b) {
		listaAdiacenta[a].push_back(b);
		listaAdiacenta[b].push_back(a);
	}

	graf_neorientat x(listaAdiacenta, n, m);

	// Afisare
	out << x.darb();
}

void eulerDriver() {
	// https://infoarena.ro/problema/ciclueuler
	// Citire
	ifstream in("ciclueuler.in");
	ofstream out("ciclueuler.out");

	int n, m;
	in >> n >> m;

	graf_neorientat x(n, m);
	in >> x;

	if (!x.isEuler()) {
		out << -1;
		return;
	}

	// Afisare
	vector<int> raspuns = x.euler();
	for (int i = 0; i < raspuns.size() - 1; i++) {
		out << raspuns[i] << " ";
	}
}

void hamiltonDriver() {
	// https://infoarena.ro/problema/hamilton
	// Citire
	ifstream in("hamilton.in");
	ofstream out("hamilton.out");

	int n, m;
	in >> n >> m;

	graf_orientat_ponderat x(n, m);
	in >> x;

	// Afisare
	vector<int> raspuns = x.hamilton();
	for (int i = 0; i < raspuns.size(); i++) {
		out << raspuns[i] << " ";
	}
}

void cuplajDriver() {
	// https://infoarena.ro/problema/cuplaj
	// Citire
	ifstream in("cuplaj.in");
	ofstream out("cuplaj.out");

	int l, r, m;
	in >> l >> r >> m;

	graf_bipartit x(l, r, m);
	in >> x;

	// Afisare
	for (auto i : x.cuplaj()) {
		out << i.first;
	}
}

int main() {
	// Se apeleaza functia corespunzatoare problemei
	cuplajDriver();
	return 0;
}