#include<cstdio>
#include<vector>

int N,M,S;

std :: vector <int> A[100005];
std :: vector <int> :: iterator it;

int COADA[100005];
int F[100005];

void read(){
	
	scanf("%d%d%d",&N,&M,&S);
	
	int x,y;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&x,&y);
		A[x].push_back(y);
	}
	
	/*for(int i=1;i<=N;i++){
		printf("%d:	",i);
		for(it=A[i].begin(); it < A[i].end(); it++)
			printf("%d ",*it);
		printf("\n");
	}*/
	
}

void solve(){
	
	F[S]++;
	
	int last = 0;
	COADA[++last] = S;
	
	int first = 1;
	int end = last;
	int nivel = 1;
	
	while(first <= last){
		
		for(int i=first;i<=end;i++)
			for(it = A[COADA[i]].begin(); it < A[COADA[i]].end(); it++)
				if(!F[*it]){
					COADA[++last] = *it;
					F[*it] = nivel;
				}
		first = end + 1;
		end = last;
		nivel ++;
		
	}
	
	
}

void write(){
	
	for(int i=1;i<=N;i++){
		if(i==S) printf("0 ");
		else if(F[i]==0) printf("-1 ");
		else printf("%d ",F[i]);
	}
	
}

int main(){
	
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	read();
	
	solve();
	
	write();
	
	return 0;
	
}