#include<stdio.h>
#include<list>
#include<deque>
using namespace std;

FILE*f=fopen("bfs.in","r");
FILE*g=fopen("bfs.out","w");

int N,M,S,final[100100],i,x,y,nr,cc;
list<int>W[100100];
deque<int> coada;
deque<int> cost;
char viz[100100];

int main () {
	
	fscanf(f,"%d %d %d",&N,&M,&S);
	
	for(i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		W[x].push_back(y);
	}
	
	list<int>::iterator itt;
	coada.push_back(S);
	cost.push_back(0);
	viz[S] = 1;
	final[S] = 0;
	
	while ( !coada.empty() ){
		nr = *coada.begin();
		cc = *cost.begin();
		
		for( itt = W[nr].begin() ; itt != W[nr].end() ; ++itt ){
			if( viz[*itt] == 0 ){
				viz[*itt] = 1;
				coada.push_back(*itt);
				cost.push_back(cc + 1);
				final[*itt] = cc + 1;
			}
			
		}
		coada.pop_front();
		cost.pop_front();
	}
	
	for( i = 1 ; i <= N ; ++i ){
		if ( final[i] == 0 )
			if ( i == S)
				fprintf(g,"0 ");
			else
				fprintf(g,"-1 ");
		else
			fprintf(g,"%d ",final[i]);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}