#include <iostream>
#include <stdio.h>
using namespace std;
long m,n,p,u,a,b,s;
int mat[1000][1000],sol[100000],cost[100000],viz[100000],i,c[100000];
FILE *f,*g;
int main()
{
f=fopen("bfs.in","r");
g=fopen("bfs.out","w");
fscanf(f,"%ld %ld %ld\n",&n,&m,&s);
for(i=1;i<=m;i++)
{fscanf(f,"%ld %ld",&a,&b);
	mat[a][b]=1;}
viz[s]=1;
sol[s]=0;
c[1]=s;
cost[1]=0;
p=1;u=1;
while(p<=u){
	for(i=1;i<=n;i++)
		if(mat[c[p]][i]==1&&viz[i]==0){u++; c[u]=i;viz[i]=1; cost[u]=cost[p]+1; sol[i]=cost[u];}
		p++;
}
for(i=1;i<=n;i++)
{if(i!=s&&sol[i]==0)sol[i]=-1;
	fprintf(g,"%ld ",sol[i]);
}
fclose(f);
fclose(g);
return 0;
}