#include <iostream>
#include <stdio.h>
#define max 100001
struct art { int val; art *urm;};
using namespace std;
FILE *f,*g;
int main()
{ 
short int viz[max];
long i,cost[max],c[max],m,n,pr,u,a,b,s,sol[max];
art *aux;
art *p[max];
f=fopen("bfs.in","r");
g=fopen("bfs.out","w");
fscanf(f,"%ld %ld %ld",&n,&m,&s);
for(i=1;i<=m;i++)
{fscanf(f,"%ld %ld",&a,&b);
	aux=new art;
	aux->val=b;
	aux->urm=p[a];
	p[a]=aux;
	}
for(i=1;i<=n;i++)
	sol[i]=-1;
viz[s]=1;
c[1]=s;
sol[s]=0;
cost[1]=0;
pr=1;u=1;
while(pr<=u){
	aux=p[c[pr]];
	while(aux!=NULL){
		if(viz[aux->val]==0){u++; c[u]=aux->val;cost[u]=cost[pr]+1;viz[aux->val]=1; sol[aux->val]=cost[u];}
	aux=aux->urm;
	}
	pr++;
}
sol[s]=0;
for(i=1;i<=n;i++){
	fprintf(g,"%ld ",sol[i]);
}
fclose(f);
fclose(g);
return 0;
}