#include <stdlib.h>
#include <stdio.h>
//queue implementation~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
typedef struct cell{
	long long data;
	struct cell* next;
}cell;

typedef struct queue{
	cell* front;
	cell* back;
}queue ;

void queue_init(queue* Q){
	Q->front=NULL;
	Q->back=NULL;
}

void queue_insert(long long val,queue* Q){
	cell* next = (cell*)malloc(sizeof(cell));
	if(Q->front==NULL){
		Q->back=next;
		Q->front=Q->back;
		Q->back->data=val;
		Q->back->next=NULL;
	}
	else{
		Q->back->next=next;
		Q->back=next;
		Q->back->data=val;
		Q->back->next=NULL;
	}
}

void queue_pop(queue* Q){
	cell* next=Q->front->next;
	if(Q->back==Q->front)Q->back=next;
	free(Q->front);
	Q->front=next;
}

long long queue_front(queue* Q){
	if(Q->front==NULL)abort();
	return Q->front->data;
}

long long min(long long a,long long b){
	if(a<b)return a;
	return b;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int main(){
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	long long n,m,start;
	scanf("%lli",&n);
	scanf("%lli",&m);
	scanf("%lli",&start);
	start--;
	queue A[100001];
	for(long long i=0;i<n;i++){
		queue_init(&A[i]);
	}
	for(long long i=0;i<m;i++){
		long long a,b;
		scanf("%lli",&a);
		scanf("%lli",&b);
		queue_insert(b-1,&A[a-1]);
	}
	/*for(long long i=0;i<n;i++){
		while(A[i].front!=NULL){
			printf("%d ",A[i].front->data);
			queue_pop(&A[i]);
		}
		printf("\n");
	}*/
	queue Q;
	queue_init(&Q);
	long long *depth,*vis;
	depth=(long long*)malloc(100001*sizeof(long long));
	vis=(long long*)malloc(100001*sizeof(long long));
	for(long long i=0;i<n;i++){
		depth[i]=100000000;
		vis[i]=0;
	}
	depth[start]=0;
	queue_insert(start,&Q);
	while(Q.front!=NULL){
		long long i=Q.front->data;
		queue_pop(&Q);
		if(vis[i])continue;
		vis[i]=1;
		while(A[i].front!=NULL){
			long long j=A[i].front->data;
			if(!vis[j]){
				depth[j]=min(depth[j],depth[i]+1);
				queue_insert(j,&Q);
			}
			queue_pop(&A[i]);
		}
	}
	
	for(long long i=0;i<n;i++)if(vis[i])printf("%lli ",depth[i]);
	else printf("-1 ");
	fclose(stdout);
	fclose(stdin);
}