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

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 + calculez distantele celorlalte varfuri fata de un varf de start

public:
	Graf(int n, int m);
	void solve_bfs_distanta_minima(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();
		// cout << varf << " ";
		coada.pop();

		for (int j = 0; j < vecini[varf].size(); j++) 
			if (!vizitat[vecini[varf][j]])
			{
				vizitat[vecini[varf][j]] = 1;

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

				distanta_minima[vecini[varf][j]] = distanta_minima[varf] + 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 nodurile 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] << " ";

}

int main()
{
	int problema;

	problema = 1;
	
	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);
	}

	return 0;
}