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

using namespace std;
int INF = (1 << 30) - 1;

class Graph
{
private:
	int n, m;
	vector<vector<pair<int, int>>> adj_list_costs; //A vector with the neighbours of all the nodes and the cost of the edges between them
	vector<vector<int>> adj_list; //A vector with the neighbours of all the nodes 
	void DFS(int source, vector<int>& order);
	void dfs_order(int source, vector<int>& order, stack<int>& topo_stack);
	void count_sort(vector<int>& connections_no);
	void dfs_ctc(int varf, vector<vector<int>>& adj_list, vector<int>& vizitat, stack<int>& result_stq);
	void transpose(int varf, vector<vector<int>>& adj_list_trans, vector<int>& order_trans, vector<vector<int>>& strongly_con_comp, int no_strongly_con_comp);
public:
	Graph(int nodes, int edges);
	void add_edge_cost(int parent, int child, int cost);
	void add_edge(int parent, int child);
	vector<int> BFS(int source);
	int connected_components();
	stack<int> topological_sort();
	void strongly_connected_components(ifstream& f, ofstream& o);
	bool havel_hakimi(vector<int>& connections_no);
	vector<int> dijkstra();
	vector<int> bellman_ford(int source);
	void roy_floyd(vector<vector<int>>& distances);
	int hamilton();
	vector<int> euler_circuit();
};

Graph::Graph(int nodes_no, int edges_no) // Initiate the values of the graph
{
	n = nodes_no;
	m = edges_no;
	adj_list_costs.resize(nodes_no + 1);
	adj_list.resize(nodes_no + 1);
}

void Graph::add_edge_cost(int parent, int child, int cost) // Adding edges and their costs in the adjacency list
{
	adj_list_costs[parent].push_back(make_pair(child, cost));
}

void Graph::add_edge(int parent, int child) // Adding edges in the adjacency list
{
	adj_list[parent].push_back(child);
}

vector<int> Graph::BFS(int source)
{
	queue<int> neighbours; //coada in care aduag pe rand nle pe care le voi parcurge in BFS
	vector<int> order(n + 1, -1);
	order[source] = 0; //costul de vizita al nodului source e 0
	neighbours.push(source); //adaug nodul source in coada BFS
	while (neighbours.empty() == false) { //cat timp am n accesibile din radacina
		int current_node = neighbours.front(); //iau nodul din fata cozii si adaug la finalul cozii toti neighboursi cu care acesta are conexiuni
		neighbours.pop();
		for (auto& neighbour_node : adj_list[current_node]) //iau din lista de adj_list nle vecine
		{
			if (order[neighbour_node] == -1) { //verific ca nodul sa nu fi fost deja vizitat
				order[neighbour_node] = order[current_node] + 1; //daca nodul nu a fost vizitat, ii calculez costul de vizita
				neighbours.push(neighbour_node);                               //si il adaug in coada pentru BFS
			}
		}
	}
	return order;
}

void Graph::DFS(int source, vector<int>& order)
{
	order[source] = 1; //marchez nodul source ca fiind vizitat
	for (auto& nod_vecin : adj_list[source]) //verific in adj_listi acestuia care nu au fost vizitati si apelez pentru fiecare in parte DFS
		if (order[nod_vecin] == -1)
		{
			order[nod_vecin] = 1; //actualizez starea nodului -> actualizat
			DFS(nod_vecin, order);
		}
}

int Graph::connected_components()
{
	vector<int> order(n + 1, -1);
	int connected_comp = 0;
	for (int i = 1; i <= n; i++) //din Graphul initial, verific nle care nu au fost vizitate si apelez DFS pentru fiecare in parte
		if (order[i] == -1)
		{
			DFS(i, order); // fiecare apel independet de DFS imi semnaleaza existenta unei componente conexe
			connected_comp++;
		}
	return connected_comp;
}

void Graph::dfs_order(int source, vector<int>& order, stack<int>& topo_stack)
{
	order[source] = 1; // pornesc dintr-un varf source, iar dupa principiul DFS, voi realiza pentru fiecare nod gasit in adancime sortarea
	for (auto& node : adj_list[source])
		if (order[node] == -1)
			dfs_order(node, order, topo_stack);
	topo_stack.push(source); //cand nodul curent a ramas fara adj_list accesibili, acesta este aduagat in stiva de sortare
}

stack<int> Graph::topological_sort()
{
	vector<int> order(n + 1, -1);
	stack<int> topo_stack;
	for (int i = 1; i <= n; i++) //din graful initial, verific nle care nu au fost vizitate si apelez Sortarea Topologica pentru fiecare in parte
		if (order[i] == -1)
			dfs_order(i, order, topo_stack);
	return topo_stack;
}

void Graph::count_sort(vector<int>& connections_no)
{
	vector<int>freq(n, 0);
	int k = 1;

	for (int i = 0; i < n; i++)
		freq[connections_no[i + 1]]++;

	for (int i = n - 1; i >= 0; i--)
		if (freq[i])
		{
			while (freq[i])
			{
				connections_no[k++] = i;
				freq[i]--;
			}
		}
}

bool Graph::havel_hakimi(vector<int>& connections_no)
{
	int elem_sum = 0;
	for (int i = 1; i <= n; i++)
	{
		elem_sum += connections_no[i];
		if (connections_no[i] >= n) // gradul fiecarui varf trebuie sa fie mai mic strict decat numarul de varfuri
			return false;
	}
	if (elem_sum % 2 == 1) // suma elementelor din vector trebuie sa fie un numar par		
		return false;

	count_sort(connections_no); // sortez descrecator secventa gradelor

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

		for (int i = 2; i <= maximum + 1; i++) // selectez cele mai mari numere din secventa gradelor (= maximum)
		{
			connections_no[i] --;
			if (connections_no[i] < 0)
				return false;
		}
		count_sort(connections_no); // sortez descrecator secventa gradelor
	}
	return true;
}

void Graph::dfs_ctc(int varf, vector<vector<int>>& adj_list, vector<int>& order, stack<int>& result_stq)
{
	order[varf] = 1; // marchez varful curent ca fiind vizitat

	for (int j = 0; j < adj_list[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!order[adj_list[varf][j]])
			dfs_ctc(adj_list[varf][j], adj_list, order, result_stq);

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

void Graph::transpose(int varf, vector<vector<int>>& adj_list_trans, vector<int>& order_trans, vector<vector<int>>& strongly_con_comp, int no_strongly_con_comp)
{
	strongly_con_comp[no_strongly_con_comp].push_back(varf);
	order_trans[varf] = 1; // marchez varful curent ca fiind vizitat
	for (int j = 0; j < adj_list_trans[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!order_trans[adj_list_trans[varf][j]])
			transpose(adj_list_trans[varf][j], adj_list_trans, order_trans, strongly_con_comp, no_strongly_con_comp);
}

void Graph::strongly_connected_components(ifstream& in, ofstream& out)
{
	vector<vector<int>>adj_list(n + 1); // liste de adiacenta
	vector<vector<int>>adj_list_trans(n + 1); // liste de adiacenta pentru graful transpus
	vector<int>order(n + 1, 0); // vector frecventa pentru vizitarea nodurilor grafului
	vector<int>order_trans(n + 1, 0); // vector frecventa pentru vizitarea nodurilor grafului transpus
	stack<int>result_stq; // stiva in care sunt stocate varfurile in ordinea descrecatoare a timpilor de finalizare

	int no_strongly_con_comp = 0;
	vector<vector<int>>strongly_con_comp(n + 1); // stocarea componentelor tare conexe

	for (int i = 0; i < m; i++)
	{
		int x, y;
		in >> x >> y;
		adj_list[x].push_back(y);
		adj_list_trans[y].push_back(x); //adaug elementele pentru adiacenta grafului transpus
	}

	for (int i = 1; i <= n; i++) // este parcurs graful cu DFS si se determina timpii de finalizare
		if (!order[i])
			dfs_ctc(i, adj_list, order, result_stq);

	while (result_stq.size()) // graful transpus este parcurs in functie de timpii de finalirizare determinati mai sus
	{
		if (!order_trans[result_stq.top()])
		{
			no_strongly_con_comp++;
			transpose(result_stq.top(), adj_list_trans, order_trans, strongly_con_comp, no_strongly_con_comp);
		}
		result_stq.pop();
	}

	out << no_strongly_con_comp << endl;

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

vector<int> Graph::dijkstra()
{
	vector<int>distances(n + 1, 1000000);
	vector<bool>vizitat(n + 1, 0);
	priority_queue<pair<int, int>> pq; //with the use of a priority queue, I simulate a max heap(all the elements will pe in a descending order)
	pq.push(make_pair(0, 1));          //and I'll always take the element from the tail
	distances[1] = 0; //the cost of the soruce code is equal with 0
	while (pq.empty() == false)
	{
		int source = pq.top().second;
		//cout << source;
		pq.pop();

		if (!vizitat[source])
		{
			vizitat[source] = 1;
			for (size_t k = 0; k < adj_list_costs[source].size(); k++) //check whether the road through an intermidiate node is shorter than the actual one
			{                                                 //if so, add the new value in distances
				pair<int, int> j = adj_list_costs[source][k];
				int destination = j.first;
				int cost = j.second;
				//cout << destination << " " << cost << endl;
				if (distances[source] + cost < distances[destination]) //if the value trhough an intermidiate node is shorter then the acual one, change the value
				{
					distances[destination] = distances[source] + cost;
					//cout << distances[destination] << endl;
					pq.push(make_pair(-distances[destination], destination)); // introduce the distance as negative integers, so the will be at the end of the pq
				}
			}
		}
	}
	return distances;
}

int Graph::hamilton() // Minimum Flow Cost Hamiltonian Cycle
{
	int final_cost = INF; // The final cost of the Hamiltonian Cycle
	int nodes_no = 1 << n;
	vector<vector<int>> costs; // costs[i][j] of minimal costs between 0 and a node j that
							   // contains exactly the nodes used in binary representation of i
	costs.resize(nodes_no);
	for (int i = 0; i < nodes_no; i++)
		for (int j = 0; j < n; j++)
			costs[i].push_back(INF);
	costs[1][0] = 0; // Let the cycle begin form the 0, so the cycle with only the node 0 has a cost of 0
	for (int i = 0; i < nodes_no; i++) // i gives the nodes of the chain
		for (int j = 0; j < n; j++)
			if ((1 << j) & i) // Check if the node is a part of the chain described by i's binary representation
			{
				for (int k = 0; k < adj_list_costs[j].size(); k++)  // Get through all the neighbours of the node
				{

					if (i & (1 << adj_list_costs[j][k].first))  // Check if the neighbour node is a part of the chain
					{
						// Actualise the minum cost - check if using the neighbouring node will get a better cost
						costs[i][j] = min(costs[i][j], costs[i ^ (1 << j)][adj_list_costs[j][k].first] +
							adj_list_costs[j][k].second);
					}
				}
			}

	for (int i = 0; i < adj_list_costs[0].size(); ++i)
		final_cost = min(final_cost, costs[nodes_no - 1][adj_list_costs[0][i].first] +
			adj_list_costs[0][i].second);
	return final_cost;
}

vector<int> Graph::euler_circuit()
{
	vector<int> euler_list;
	for (int i = 1; i <= n; i++) // Check the first condition for the graph to be eulerian: all its nodes must have an even number of neighbours
		if (adj_list_costs[i].size() % 2 == 1)
		{
			euler_list.push_back(-1);
			return euler_list;
		}
	vector<int> erased;
	erased.resize(m);
	for (int i = 1; i <= m; i++)
		erased.push_back(0);
	stack<int> aux;
	aux.push(1); // Add the beginning node in the cycle
	while (aux.empty() == false)
	{
		int node = aux.top();
		if (adj_list_costs[node].empty() == false)
		{
			pair<int, int> edge = adj_list_costs[node].back(); // Take the edge and its orderd no so that i can erase it from the list
			adj_list_costs[node].pop_back();
			if (erased[edge.second] == 0) // Mark the erased edges
			{
				aux.push(edge.first);
				erased[edge.second] = 1;
			}
		}
		else
		{
			euler_list.push_back(node);
			aux.pop();
		}
	}
	return euler_list;
}

void Graph::roy_floyd(vector<vector<int>>& distances)
{
	for (int i = 1; i <= n; i++) //nod intermediar al drumului
		for (int a = 1; a <= n; a++) //nodul de start pentru drum
			for (int b = 1; b <= n; b++) //nodul final al drumului
				if (distances[a][b] > distances[a][i] + distances[i][b]) //daca lungimea drumului actual este mai mare decat al celui                                                      
					distances[a][b] = distances[a][i] + distances[i][b]; //ce trece print-un nod intermediar, actualizez distanta si nr de drumuri
}

vector<int> Graph::bellman_ford(int start)
{
	vector<int> distances(n + 1, INF); //lsita cu costul minimal de la i la j
	distances[start] = 0;
	queue<int> q;
	vector<int> in_q(n+1, 0);
	vector<int> freq(n+1, 0); // verificam de cate ori a fost relaxat un varf
	q.push(start);
	in_q[start] = 1;
	int ok = 1;
	while ((q.empty() == false) && (ok == 1))
	{
		int source = q.front();
		q.pop();
		in_q[source] = 0;

		for (int i = 0; i < adj_list_costs[source].size(); i++)
		{
			pair <int, int> p = adj_list_costs[source][i];
			int destination = p.first;
			int cost = p.second;

			if ( distances[source] + cost < distances[destination])
			{
				distances[destination] = distances[source] + cost;
				if (in_q[destination] == 0)
				{
					q.push(destination);
					in_q[destination] = 1;
					freq[destination]++;
					if (freq[destination] > n) //verific daca exista ciclu negativ
					{
						ok = 0;
						distances[1] = INF;
						break;
					}
				}
			}
		}
	}
	return distances;
}

int main()
{
	int option = 7;

	//BFS Algorithm - https://infoarena.ro/problema/bfs - 80p
	if (option == 1)
	{
		int n, m, s;
		ifstream in("bfs.in");
		ofstream out("bfs.out");
		in >> n >> m >> s;
		Graph g(n, m); //initializez graful
		for (int i = 0; i < m; i++)
		{
			int x, y;
			in >> x >> y;
			g.add_edge(x, y);
		}
		in.close();
		vector<int> result = g.BFS(s);
		for (int i = 1; i <= n; i++)
			out << result[i] << " ";
		out.close();
	}
	//DFS Algorithm - connected components - https://infoarena.ro/problema/dfs - 100p
	if (option == 2)
	{
		int n, m;
		ifstream in("dfs.in");
		ofstream out("dfs.out");
		in >> n >> m;
		Graph g(n, m); //initializez graful
		for (int i = 0; i < m; i++)
		{
			int x, y;
			in >> x >> y;
			g.add_edge(x, y);
		}
		in.close();
		out << g.connected_components();
		out.close();
	}
	//Topological sort - https://infoarena.ro/problema/sortaret - 100p
	if (option == 3)
	{
		int n, m;
		ifstream in("sortaret.in");
		ofstream out("sortaret.out");
		in >> n >> m;
		Graph g(n, m); //initializez graful
		for (int i = 0; i < m; i++)
		{
			int x, y;
			in >> x >> y;
			g.add_edge(x, y);
		}
		in.close();
		stack<int> result = g.topological_sort();
		while (result.empty() == false)
		{
			out << result.top() << " ";
			result.pop();
		}
		out.close();
	}
	//Havel Hakimi 
	if (option == 4)
	{
		int n;
		ifstream in("hh.in");
		ofstream out("hh.out");
		in >> n;
		Graph g(n, 0); //initializez graful
		vector<int>connections_no(n + 1);
		for (int i = 1; i <= n; i++)
			in >> connections_no[i];
		in.close();
		if (g.havel_hakimi(connections_no))
			out << "DA";
		else
			out << "NU";
		out.close();
	}
	//Strongly connected components: https://infoarena.ro/problema/ctc - 100p
	if (option == 5)
	{
		ifstream in("ctc.in");
		ofstream out("ctc.out");
		int n, m;
		in >> n >> m;
		Graph g(n, m);
		g.strongly_connected_components(in, out);
		in.close();
		out.close();
	}
	//Djikstra Algorithm - https://www.infoarena.ro/problema/dijkstra - 100p
	if (option == 6)
	{
		int n, m;
		ifstream in("dijkstra.in");
		ofstream out("dijkstra.out");
		in >> n >> m;
		Graph g(n, m);
		for (int i = 0; i < m; i++) // Reading each edge and adding its order
		{
			int parent, child, cost;
			in >> parent >> child >> cost;
			g.add_edge_cost(parent, child, cost);
		}
		in.close();
		vector<int> result = g.dijkstra();
		for (int i = 2; i <= n; i++)
			if (result[i] == 1000000)
				out << 0 << " ";
			else out << result[i] << " ";
		out.close();
	}
	//Bellman-Ford Algorithm - https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
	if (option == 7)
	{
		int n, m;
		ifstream in("bellmanford.in");
		ofstream out("bellmanford.out");
		in >> n >> m;
		Graph g(n, m);
		for (int i = 0; i < m; i++)
		{
			int x, y, cost;
			in >> x >> y >> cost;
			g.add_edge_cost(x, y, cost);
		}
		in.close();
		int ok = 1;
		vector<int> result = g.bellman_ford(1);
		if (result[1] != INF)
			for (int i = 2; i <= n; i++)
				out << result[i] << " ";
		else
			out << "Ciclu negativ!";
		out.close();
	}
	//Roy-Floyd Algorithm - https://infoarena.ro/problema/royfloyd - 100p
	if (option == 8)
	{
		ifstream in("royfloyd.in"); //citirea datelor din fisier
		ofstream out("royfloyd.out");
		int n;
		in >> n;
		Graph g(n, 0);
		vector<vector<int>>distances(n + 1, vector<int>(n + 1)); // matricea distantelor
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				int aux;
				in >> aux;
				if (i != j && aux == 0)
					distances[i][j] = INF;
				else
					distances[i][j] = aux;
			}
		in.close();

		g.roy_floyd(distances);

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				if (distances[i][j] == INF)
					out << 0 << " ";
				else
					out << distances[i][j] << " ";
			out << endl;
		}
		out.close();
	}
	// Minimum Flow Cost Hamiltonian Cycle - https://www.infoarena.ro/problema/hamilton - 100p
	if (option == 9)
	{
		int n, m;

		ifstream in("hamilton.in");
		ofstream out("hamilton.out");

		in >> n >> m;
		Graph g(n, m);
		for (int i = 0; i < m; i++) // Reading each edge with its own cost
		{
			int parent, child, cost;
			in >> parent >> child >> cost;
			g.add_edge_cost(parent, child, cost);
		}
		int final_cost = g.hamilton(); // Check whether there are any Hamiltonian Cycles and return the minimal value found
		if (final_cost != INF)
			out << final_cost;
		else
			out << "Nu exista solutie";
		in.close();
		out.close();
	}
	// Eulerian ciurcuit - https://www.infoarena.ro/problema/ciclueuler - 100p
	if (option == 10)
	{
		int n, m;
		ifstream in("ciclueuler.in");
		ofstream out("ciclueuler.out");
		in >> n >> m;
		Graph g(n, m);
		for (int i = 0; i < m; i++) // Reading each edge and adding its order
		{
			int parent, child;
			in >> parent >> child;
			g.add_edge_cost(parent, child, i + 1);
			g.add_edge_cost(child, parent, i + 1);
		}
		in.close();
		vector<int> euler_list = g.euler_circuit();
		for (int i = 0; i < euler_list.size(); i++)
		{
			out << euler_list[i] << " ";
		}
		out.close();
	}
	return 0;
}