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

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

int N,M,S,cost[100100],i,x,y,nr,cc,coada[100100],p,u;
list<int>W[100100];

void citire (){
	
	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);
	}
	//for ( i = 1 ; i <= N ; ++i )
	//	nrvecini[i] = W[i].size();
	
}

void scriere () {
	for( i = 1 ; i <= N ; ++i ){
		if ( cost[i] == 0 )
			if ( i == S)
				fprintf(g,"0 ");
			else
				fprintf(g,"-1 ");
		else
			fprintf(g,"%d ",cost[i]);
	}
	
}

void BFS () {
	
	memset(cost,-1,sizeof(cost));
	p = u = 1;
	cost[S] = 0;
	coada[1] = S;
	
	list<int>::iterator itt;
	
	while( p <= u ){
		
		for ( itt = W[coada[p]].begin() ; itt != W[coada[p]].end() ; ++itt ){
			if(cost[*itt] == -1 ){
				coada[++u] = *itt;
				cost[*itt] = cost[coada[p]] + 1;
			}
		}
		
		
		++p;
	}
	
	
}


int main () {
	
	citire();
	BFS();
	scriere();
	
	fclose(f);
	fclose(g);
	
	return 0;
}