#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <deque>
using namespace std;


long long n , m , s , x , y , cost[100005];

int main ()
{
	ifstream f ("bfs.in");
	ofstream g ("bfs.out");
	
	vector < int > a[100005];
	deque < int > coada;

	memset (cost , - 1 , sizeof(cost));
	
	f >> n >> m >> s;
	
	for (long long i = 1 ; i <= m ; ++i)
	{
		f >> x >> y;
		a[x].push_back(y);
	}
	
	coada.push_back(s);
	cost[s] = 0;
	
	while (coada.size())
	{
		int nod = coada[0];
		
		for (unsigned i = 0 ; i < a[nod].size() ; ++i)
		{
			if (cost[a[nod][i]] != -1)
				continue;
				
			cost[a[nod][i]] = cost[nod] + 1;
			coada.push_back(a[nod][i]);
		}
		coada.pop_front();
	}
	
	for (int i = 1 ; i <= n ; ++i)
		g << cost[i] << " ";
	
	return 0;
}