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

using namespace std;

class Graf
{
	int noduri, muchii;

	void bfs_si_distante(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& distanta_minima); // parcurgere in latime + determinarea distantelor celorlalte varfuri fata de un varf de start
	void dfs(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat); // parcurgere in adancime
	void dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat); // parcurgere in adancime + determinarea timpilor de finalizare: momentul cand se termina de vizitat vecinii unui varf x (si toti vecinii/descendentii acestora), iar varful x este eliminat de pe stiva
	void dfs_graf_transpus(int varf, vector<vector<int>>& vecini_transpus, vector<bool>& vizitat_transpus, vector<vector<int>>& componente_tare_conexe, int nr_componenete_tare_conexe); // parcurgere in adancime a grafului transpus + memorarea componentelor tare conexe

public:
	Graf(int n, int m);
	void solve_bfs_distanta_minima(ifstream& f, ofstream& o);
	void solve_componente_conexe(ifstream& f, ofstream& o);
	void solve_sortare_topologica(ifstream& f, ofstream& o);
	void solve_componente_tare_conexe(ifstream& f, ofstream& o);

};

Graf::Graf(int n, int m)
{
	noduri = n;
	muchii = m;
}

void Graf::bfs_si_distante(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& distanta_minima)
{
	queue<int>coada; // coada in care salvez varfurile care sunt vizitate si care urmeaza sa fie explorate(adica cercetez vecinii lor)

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

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

	while (coada.size()) // cat timp mai am noduri de explorat
	{
		varf = coada.front(); // extrag un varf din coada pentru a-l explora
		
		// cout << varf << " "; 
		
		coada.pop();

		for (int j = 0; j < vecini[varf].size(); j++) //marchez toate varfurile adiacente cu el si nevizitate anterior, iar apoi le introduc in coada
			if (!vizitat[vecini[varf][j]])
			{
				vizitat[vecini[varf][j]] = 1;

				coada.push(vecini[varf][j]);

				distanta_minima[vecini[varf][j]] = distanta_minima[varf] + 1; // distanta unui varf nou adaugat este distanta varfului care l-a adaugat + 1
			}
	}
}

void Graf::solve_bfs_distanta_minima(ifstream& f, ofstream& o)
{
	int varf_start; // varful din care trebuie sa incepem parcurgerea

	f >> varf_start;

	vector<vector<int>>vecini; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate
	vector<int>distanta_minima; // vector in care stochez distantele fata de varful de start

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

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y); 
	}

	for (int i = 1; i <= noduri; i++) 
		sort(vecini[i].begin(), vecini[i].end());

	bfs_si_distante(varf_start, vecini, vizitat, distanta_minima);

	for (int i = 1; i <= noduri; i++)
		if (i != varf_start && distanta_minima[i] == 0)
			o << "-1 ";
		else
			o << distanta_minima[i] << " ";

}

void Graf::dfs(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat)
{
	// cout << varf << " ";

	vizitat[varf] = 1; // marchez varful de start ca fiind vizitat
	
	for (int j = 0; j < vecini[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat[vecini[varf][j]])
			dfs(vecini[varf][j], vecini, vizitat);
}

void Graf::solve_componente_conexe(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate

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

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;

		vecini[x].push_back(y);
		vecini[y].push_back(x);

	}

	for (int i = 1; i <= noduri; i++)
		sort(vecini[i].begin(), vecini[i].end());

	int componenete_conexe = 0;

	for(int i = 1; i <= noduri; i++) // pentru fiecare varf ramas nevizitat incrementez variabila componente_conexe si apelez functia de parcurgere in adancime
		if (!vizitat[i])
		{
			componenete_conexe += 1;

			dfs(i, vecini, vizitat);
		}
	
	o << componenete_conexe; 
}	

void Graf::dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat)
{
	// cout << varf << " ";

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

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

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

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

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

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);
	}

	for (int i = 1; i <= noduri; i++)
		sort(vecini[i].begin(), vecini[i].end());

	for (int i = 1; i <= noduri; i++)
		if (!vizitat[i])
			dfs_si_timp_de_finalizare(i, vecini, vizitat, stiva_rezultat);

	while (stiva_rezultat.size()) 
	{
		o << stiva_rezultat.top() << " ";
		stiva_rezultat.pop();
	}
}

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

	componente_tare_conexe[nr_componenete_tare_conexe].push_back(varf);

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

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

}

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


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

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);
		
		vecini_transpus[y].push_back(x);
	}

	for (int i = 1; i <= noduri; i++)
	{
		sort(vecini[i].begin(), vecini[i].end());
		sort(vecini_transpus[i].begin(), vecini_transpus[i].end());
	}

	for (int i = 1; i <= noduri; i++) // este parcurs graful si se determina timpii de finalizare 
		if (!vizitat[i])
			dfs_si_timp_de_finalizare(i, vecini, vizitat, stiva_rezultat);

	while (stiva_rezultat.size()) // graful transpus este parcurs in functie de timpii de finalirizare determinati mai sus
	{
		if (!vizitat_transpus[stiva_rezultat.top()])
		{
			nr_componenete_tare_conexe++;
			dfs_graf_transpus(stiva_rezultat.top(), vecini_transpus, vizitat_transpus, componente_tare_conexe, nr_componenete_tare_conexe);
		}

		stiva_rezultat.pop();
	}

	o << nr_componenete_tare_conexe << "\n";

	for (int i = 1; i <= noduri; i++)
	{
		if (componente_tare_conexe[i].size())
		{
			for (int j = 0; j < componente_tare_conexe[i].size(); j++)
				o << componente_tare_conexe[i][j] << " ";
			o << "\n";
		}
	}
}

int main()
{
	int problema;

	problema = 4;
	
	if (problema == 1) //BFS - Parcurgere in latime
	{
		ifstream f("bfs.in");
		ofstream o("bfs.out");
		
		int noduri, muchii;
		
		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_bfs_distanta_minima(f, o);
	}

	else if (problema == 2) // Parcurgere DFS - componente conexe
	{
		ifstream f("dfs.in");
		ofstream o("dfs.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_componente_conexe(f, o);
	}

	else if (problema == 3) // Sortare topologica
	{
		ifstream f("sortaret.in");
		ofstream o("sortaret.out");

		int noduri, muchii;
		
		f >> noduri >> muchii; 

		Graf g(noduri, muchii);

		g.solve_sortare_topologica(f, o);

	}

	else if (problema == 4) // Componente tare conexe
	{
		ifstream f("ctc.in");
		ofstream o("ctc.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);
		
		g.solve_componente_tare_conexe(f, o);
	}

	return 0;
}