#include <stdio.h>
#include <stdlib.h>
long n,m,i,j,s,p,q,nod,x[1000002],y[1000002];
long * v[100002];
long g[100002],niv[100002],st[100002];
int main(){
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%ld %ld %ld",&n,&m,&s);
    for (i=1;i<=m;++i)
        scanf("%ld %ld",&x[i],&y[i]),g[x[i]]++;
    for (i=1;i<=n;++i){v[i]=(long*)malloc(g[i]*sizeof(long));g[i]=0;}
    for (i=1;i<=m;++i)v[x[i]][g[x[i]]++]=y[i];
    niv[s]=1;
    st[1]=s;p=1;q=1;
    while (p<=q){
      nod=st[p];
      for (i=0;i<g[nod];++i)
          if (!niv[v[nod][i]]){st[++q]=v[nod][i];niv[v[nod][i]]=niv[nod]+1;}
      p++;
    }
    for (i=1;i<=n;++i)printf("%ld ",niv[i]-1);
return 0;
}