#include<stdio.h>
#include<stdlib.h>
  int N,M,S;
  int *viz,*cost;
  struct nod{
  	int val;
  	nod *next;
  };
  nod **A;
   struct queue{
		int val;
		queue *next;
	};
queue *p=NULL,*prim=NULL,*ultim=NULL;
void push(int x) {
	queue *nou;
	if(prim==NULL) {
		nou= new queue;
		nou->val=x;
		nou->next=NULL;
		prim=nou;
		ultim=nou;
	}
	else {
		nou= new queue;
		nou->val=x;
		nou->next=NULL;
		ultim->next=nou;
		ultim=nou;
	}
}
int pop() {
	int x;
	x=prim->val;
	prim=prim->next;
	return x;
}
int isEmpty() {
if (prim==NULL)
		return 0;
return 1;
}
void citire() {
	nod *nou;
	int i,x,y;
	scanf("%d %d %d",&N,&M,&S);
	A=(nod**)malloc((N+1)*sizeof(nod*));
	for(i=1;i<=N;i++)
				A[i]=NULL;
		for(i=1;i<=M;i++) {
			scanf("%d %d",&x,&y);
			nou=new nod;
			nou->val=y;
			nou->next=A[x];
			A[x]=nou;
		}
	viz=(int*)calloc((N+1),sizeof(int));
	cost=(int*)malloc((N+1)*sizeof(int));
}
void bfs() {
	int i;
	int x;
	nod *q;
	for(i=1;i<=N;i++)
			cost[i]=-1;
			cost[S]=0;
			viz[S]=1;
			push(S);
		while(isEmpty()) {
			x=pop();
			q=A[x];
			while(q!=NULL) {
				if (viz[q->val]==0) {
					push(q->val);
					cost[q->val]=cost[x]+1;
					viz[q->val]=1;
				}
			q=q->next;
			}
		}
}
int main () {
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
int i,j;
	citire();
	bfs();
for(i=1;i<=N;i++)
	printf("%d ",cost[i]);
fclose(stdin);
fclose(stdout);
return 0;
}