#include<stdio.h>

#define NM 100000
#define MM 1000000
struct edge{
	int a,b;
	};
edge v[MM+1];
int pv[NM+1];
int n,m,s;
int t[NM+1],li=1,ls;
int c[NM+1],viz[NM+1];

int cvida(){return li>ls;}
void pune(int x){t[++ls]=x;viz[x]=1;}
int scoate(){return t[li++];}

void poz(int st,int dr,int&piv){
int i=st,j=dr,d=0;
edge aux;
while(i<j){
	if(v[i].a>v[j].a||v[i].a==v[j].a&&v[i].b>v[j].b){
		aux=v[i],v[i]=v[j],v[j]=aux,d=1-d;
		}
	i+=d,j-=1-d;
	}
piv=i;
}
void qsrt(int li,int ls){
int piv;
if(li<ls){
	poz(li,ls,piv);
	qsrt(li,piv-1);
	qsrt(piv+1,ls);
	}
}

int main(){
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
int i,j,x;
scanf("%d%d%d",&n,&m,&s);
for(j=1;j<=m;++j) {
	scanf("%d%d",&v[j].a,&v[j].b);
	}
qsrt(1,m);
for(j=1;j<=m;++j){
	x=v[j].a;
	if(!pv[x]) pv[x]=j;
	}
pune(s);
while(!cvida()){
	x=scoate();
	i=pv[x];
	while(i<=m&&v[i].a==x){
		j=v[i].b;
		if(!viz[j]) pune(j),c[j]=c[x]+1;
		i++;
		}
	}
for(i=1;i<=n;++i)
	if(!c[i]) c[i]=-1;
c[s]=0;
for(i=1;i<=n;++i) printf("%d ",c[i]);
return 0;
}