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