#include <stdio.h>
#include <stdlib.h>

////////////// QUEUE ///////////////////

typedef struct tagNode{
	int node;
	struct tagNode* next;
}Node;

typedef struct tagQueue{
	Node *start;
	Node *end;
}Queue;

void initQueue(Queue *q)
{
	q->start = NULL;
	q->end = NULL;
}

void pushQueue(Queue *q, int value)
{
	Node *new = malloc(sizeof(Node));
	new->node = value;
	new->next = NULL;
	
	if( q->start == NULL ){		
		q->start = new;
		q->end = new;		
	}
	else{
		q->end->next = new;
		q->end = new;		
	}	
}

int popQueue(Queue *q)
{
	int ret = q->start->node;
	if( q->start == q->end ){
		free(q->start);
		q->start = NULL;
		q->end = NULL;
	}
	else{
		Node *toDel = q->start;
		q->start = q->start->next;
		free(toDel);
	}
	return ret;	
}

int isEmptyQueue(Queue *q)
{
	return q->start == NULL;
}

////////////////////////////////////////


#define MAXN 100001

int M,N,S;
int dist[MAXN];

Queue vecini[MAXN];
Queue queue;


int main(int argc, char* argv[])
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	scanf("%d %d %d",&N,&M,&S);
	
	int i,a,b;
	
	for(i=1;i<=N;i++){
		initQueue(&vecini[i]);
		dist[i] = -1;
	}
	dist[S] = 0;
	
	for(i=0;i<M;i++){
		scanf("%d %d",&a,&b);
		pushQueue(&vecini[a],b);
	}
	
	pushQueue(&queue, S);
	
	while( !isEmptyQueue(&queue)){
		int node = popQueue(&queue);
		int curDist = dist[node];
		
		Node* q = vecini[node].start;
		while( q != NULL){
			int vec = q->node;
			if( dist[vec] == -1 ){
				dist[vec] = curDist+1;
				pushQueue(&queue,vec);
			}
			q = q->next;
		}
	}
	
	for(i=1;i<=N;i++){
		printf("%d ",dist[i]);
	}
	
	return 0;
}