#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 topological_sort(int source, vector<int>& order, stack<int>& topo_stack);
	void count_sort(vector<int>& connections_no);
	void dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat);
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> sort();
	void solve_componente_tare_conexe(ifstream& f, ofstream& o);
	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);
	bool havel_hakimi(vector<int>& connections_no);
	vector<int> dijkstra();
	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 vecinii 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::topological_sort(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)
			topological_sort(node, order, topo_stack);
	topo_stack.push(source); //cand nodul curent a ramas fara vecini accesibili, acesta este aduagat in stiva de sortare
}

stack<int> Graph::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)
			topological_sort(i, order, topo_stack);
	return topo_stack;
}

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::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::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::dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat)
{
	// cout << varf << " ";

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

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

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

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

	componente_tare_conexe[nr_componenete_tare_conexe].push_back(varf);

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

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

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

	for (int i = 0; i < m; 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 <= n; i++)  // sortez listele de adiacenta pentru a alegere mereu varfurile in ordine lexicografica
	//{
		//sort(vecini[i].begin(), vecini[i].end());
		//sort(vecini_transpus[i].begin(), vecini_transpus[i].end());
	//}

	for (int i = 1; i <= n; 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 <= n; 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";
		}
	}
}


int main()
{	
	//BFS Algorithm - https://infoarena.ro/problema/bfs
	/*
	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
	/*
	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
	/*
	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.sort();
	while (result.empty() == false)
	{
		cout << result.top()<< " ";
		result.pop();
	}
	out.close();*/
	//Havel Hakimi
	/*
	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
	ifstream f("ctc.in");
	ofstream o("ctc.out");

	int n, m;

	f >> n >> m;

	Graph g(n, m);

	g.solve_componente_tare_conexe(f, o);
	/*vector<vector<int>> adj_list_trans(n + 1); // liste de adiacenta pentru graful transpus
	for (int i = 0; i < m; i++)
	{
		int x, y;
		in >> x >> y;
		g.add_edge(x, y);
		adj_list_trans[y].push_back(i);
	}
	in.close();
	g.s_connected_components(adj_list_trans);
	out.close();*/
	//Djikstra Algorithm - https://www.infoarena.ro/problema/dijkstra
	/*
	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(); */
	//Roy-Floyd Algorithm - https://infoarena.ro/problema/royfloyd
	/*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
	/*
	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
	/*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;
}