#include <fstream>
#include <string>
#include <deque>
#include <vector>

using namespace std;


#define PF pop_front
#define PB push_back
#define maxN 100005


int cost[maxN];
int N, M, S;
deque < int > coada;
vector < int > lista[maxN];


void bfs ()
{
	coada.PB (S);
	
	memset ( cost, -1, sizeof (cost) );
	
	cost[S] = 0;
	
	for ( ; coada.size(); )
	{
		int nod = coada[0];
		
		for (unsigned int i = 0; i < lista[nod].size(); ++ i)
		{
			if ( cost[lista[nod][i]] != -1 )
				continue;
			
			coada.PB ( lista[nod][i] );
			
			cost[lista[nod][i]] = cost[nod] + 1;
		}
		
		coada.PF ();
	}
}


int main()
{
	ifstream f("bfs.in");
	ofstream g("bfs.out");
	
	f >> N >> M >> S;
	
	for (int i = 1; i <= M; ++ i)
	{
		int x, y;
		
		f >> x >> y;
		
		lista[x].PB(y);
	}
	
	bfs ();
	
	
	for (int i = 1; i <= N; ++ i)
		g << cost[i] << " ";
	
	
	f.close();
	g.close();
	
	return 0;
}