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

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

/* Sources:
	https://www.pbinfo.ro/articole/?eticheta=11 - Roy Floyd, Strongly Connected Components
	https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
	https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
	https://www.geeksforgeeks.org/cpp-program-for-topological-sorting/
	https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
	https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/?ref=lbp
	https://slaystudy.com/hierholzers-algorithm/
	https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/
*/

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);
	void tree_diameter(int source, int& diameter, int& last_node);
	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; // the queue in which i store the neighbours
	vector<int> order(n + 1, -1); // the list in which I track the visited nodes
	order[source] = 0; // the distance to the source is 0
	neighbours.push(source); // add the node to the queue
	while (neighbours.empty() == false)
	{   // start from the actual node add all its neighbours to the queue
		int current_node = neighbours.front(); 
		neighbours.pop();
		for (auto& neighbour_node : adj_list[current_node])
		{
			if (order[neighbour_node] == -1) // check if the node was visitied
			{ 
				order[neighbour_node] = order[current_node] + 1; //actualise the distance of the node
				neighbours.push(neighbour_node);                 //and add it to the queue
			}
		}
	}
	return order;
}

void Graph::DFS(int source, vector<int>& order)
{
	order[source] = 1; // the source node is visited
	for (auto& nod_vecin : adj_list[source]) // for each neighbourgh, see which were not visited and start to execute DFS on them
		if (order[nod_vecin] == -1)
		{
			order[nod_vecin] = 1;
			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++) // from the initial Graph, check which nodes weren't visited and execute dfs on them (each individual dfs means the componente is connected)
		if (order[i] == -1)
		{
			DFS(i, order);
			connected_comp++;
		}
	return connected_comp;
}

void Graph::dfs_order(int source, vector<int>& order, stack<int>& topo_stack)
{
	order[source] = 1; // execute the DFS from the source
	for (auto& node : adj_list[source])
		if (order[node] == -1)
			dfs_order(node, order, topo_stack);
	topo_stack.push(source); // when the are no neighbours left, add the node in the stack 
}

stack<int> Graph::topological_sort()
{                                  // execute DFS on all unvisited nodes and track their finish time
	vector<int> order(n + 1, -1);  // the list in which I track the visited nodes
	stack<int> topo_stack; // the stack where I track the order of elements in DFS =>> topological sort
	for (int i = 1; i <= n; i++) // execute DFS for all unvisited neighbours
		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++) // declare a frequency vector to store the number of nodes with the same degree
		freq[connections_no[i + 1]]++;

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

bool Graph::havel_hakimi(vector<int>& connections_no)
{
	int elem_sum = 0; //a variable to compute the sum of all the degrees
	for (int i = 1; i <= n; i++)
	{
		elem_sum += connections_no[i];
		if (connections_no[i] >= n) // the degree of each node must be at most n-1
			return false;
	}
	if (elem_sum % 2 == 1) // the sum of all degres must be an even number		
		return false;

	count_sort(connections_no); // descending sort of the degrees

	while (connections_no[1] > 0) // while the are still edges
	{
		int maximum = connections_no[1]; // maximum no of edges
		connections_no[1] = 0; // free the node with the maxim no of degrees

		for (int i = 2; i <= maximum + 1; i++) // for the next MAXIMUM no of nodes, take one from their degree
		{
			connections_no[i] --;
			if (connections_no[i] < 0) // if there are no more nodes available, edn the program
				return false;
		}
		count_sort(connections_no); // count sort on the degrees and repeat the program
	}
	return true;
}

void Graph::dfs_ctc(int varf, vector<vector<int>>& adj_list, vector<int>& order, stack<int>& result_stq) // dfs that stores the finish time of each node - the same as the topological sort
{
	order[varf] = 1; // visit the begining node

	for (int j = 0; j < adj_list[varf].size(); j++) // choose the first neighbour and compute DFS
		if (!order[adj_list[varf][j]])
			dfs_ctc(adj_list[varf][j], adj_list, order, result_stq); 

	result_stq.push(varf); // when there are no neighbours left, add thme tot the stack
}

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; // visit the begining node
	for (int j = 0; j < adj_list_trans[varf].size(); j++) // choose the first neighbour and compute DFS
		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); // store the visited nodes and return them as a strongly connected components
}

void Graph::strongly_connected_components(ifstream& in, ofstream& out)
{
	vector<vector<int>>adj_list(n + 1); // adjiency list
	vector<vector<int>>adj_list_trans(n + 1); // adjiency list for the transpose graph
	vector<int>order(n + 1, 0); // frequency vector for tracking the visited status of the graph
	vector<int>order_trans(n + 1, 0); // frequency vector for tracking the visited status of the transpose graph
	stack<int>result_stq; // stack to store the nodes in the revers order of thei finish time in DFS

	int no_strongly_con_comp = 0; // no of strongly connected components
	vector<vector<int>>strongly_con_comp(n + 1); // a list of strongly connected components

	for (int i = 0; i < m; i++) // read the adjiency list and the transpose adjiency list
	{
		int x, y;
		in >> x >> y;
		adj_list[x].push_back(y);
		adj_list_trans[y].push_back(x); 
	}

	for (int i = 1; i <= n; i++) // DFS for the nodes and get their finish time in result_staq
		if (!order[i])
			dfs_ctc(i, adj_list, order, result_stq);

	while (result_stq.size()) // we get the elements from the end of the stack and compute transpose on them (dfs without stack) 
	{                         // and the result from the transpose returns us an strongly connected component
		if (!order_trans[result_stq.top()])
		{
			no_strongly_con_comp++; // each computed transpose = one strongly connected componenet 
			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; // output the result

	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
}

void Graph::tree_diameter(int source, int& diameter, int& last_node)
{
	queue<int> q; //queue used to store the nodes for bfs
	q.push(source); //start from the source given: fisrt, an arbitrary given node, and second, from the farthest node
	vector<int> order(n + 1, 0); // a list o frequency of the visited nodes
	order[source] = 1; //the first node is visited
	vector<int> distances(n + 1, 0); // a list of distances of all the nodes from the source node
	distances[source] = 1; // the source node has distance = 1
	while (q.empty() == false) 
	{
		int parent_node = q.front(); // get the parent node and all its neighbouring nodes and compute the distance to them if they were not visited
		for (int i = 0; i < adj_list[parent_node].size(); i++) 
		{
			int current_node = adj_list[parent_node][i]; //get the current node
			if (order[current_node] == 0) //check whether it was visited
			{
				order[current_node] = 1; //change the distances and visited status and add it to the queue to get its neighbouring nodes visited
				q.push(current_node);
				distances[current_node] = distances[parent_node] + 1;
				diameter = distances[current_node]; //the final diameter will be the one of the last node, as the bfs goes down in the tree level by level
				last_node = current_node;
			}
		}
		q.pop();
	}
}

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 = 2;

	//BFS Algorithm - https://infoarena.ro/problema/bfs - 100p
	// Complexity - O(n+m)
	if (option == 1)
	{
		int n, m, s;
		ifstream in("bfs.in"); // input file
		ofstream out("bfs.out"); // output file
		in >> n >> m >> s;
		Graph g(n, m); // initialise the graph
		for (int i = 0; i < m; i++) // read the edges
		{
			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
	// Complexity - O(n+m)
	if (option == 2)
	{
		int n, m;
		ifstream in("dfs.in"); // input file
		ofstream out("dfs.out"); // output file
		in >> n >> m;
		Graph g(n, m); // initialise the graph
		for (int i = 0; i < m; i++) // read the edges
		{
			int x, y; 
			in >> x >> y;
			g.add_edge(x, y);
			g.add_edge(y, x);
		}
		in.close();
		out << g.connected_components();
		out.close();
	}

	//Topological sort - https://infoarena.ro/problema/sortaret - 100p
	// Complexity - O(n+m)
	// the graph must not contain cycles
	if (option == 3)
	{
		int n, m;
		ifstream in("sortaret.in"); // input file
		ofstream out("sortaret.out"); // output file
		in >> n >> m;
		Graph g(n, m); // initialise the graph
		for (int i = 0; i < m; i++) // read the edges
		{
			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
	// Complexity: O(n^2) - for each node(exectue count sort)
	// From a given list of n numbers that contains the degrese of a graph's node, compute if there given graph exists; 
	if (option == 4)
	{
		int n;
		ifstream in("hh.in"); //input file
		ofstream out("hh.out"); //output file
		in >> n;
		Graph g(n, 0); //initialise the graph
		vector<int>connections_no(n + 1);
		for (int i = 1; i <= n; i++) //read the degrees of the nodes
			in >> connections_no[i]; 
		in.close();
		if (g.havel_hakimi(connections_no)) //call havel hakimi to verify the given graph
			out << "DA";
		else
			out << "NU";
		out.close();
	}

	//Strongly connected components: https://infoarena.ro/problema/ctc - 100p - Kosaraju
	// Complexity: O(n+m)
	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 -100p *
	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();
	}

	//Longest path in a tree - https://www.infoarena.ro/problema/darb - 100p *
	if (option == 8)
	{
		int n;
		ifstream in("darb.in");
		ofstream out("darb.out");
		in >> n;
		Graph g(n, n-1);
		for (int i = 0; i < n - 1; i++)
		{
			int x, y;
			in >> x >> y;
			g.add_edge(x, y);
			g.add_edge(y, x);
		}
		in.close();
		int first_diameter = 0, first_last_node = 0, second_diameter = 0, second_last_node = 0;
		g.tree_diameter(1, first_diameter, first_last_node); // Execute the first BFS to find the farthest node in the whole tree and save its position
		//cout << first_diameter << endl;
		g.tree_diameter(first_last_node, second_diameter, second_last_node); // Execute the second BFS from the farthest node in the tree to get the second farthest node and 
		//cout << second_last_node << endl;                                  // calculate its diameter (distance between the 2 nodes)
		//cout << second_diameter << endl;
		out << second_diameter;
		out.close();
	}

	//Roy-Floyd Algorithm - https://infoarena.ro/problema/royfloyd - 100p *
	if (option == 9)
	{
		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 == 10)
	{
		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 == 11)
	{
		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;
}