#include<stdio.h>
#include<stdlib.h>

int *a[100001],n,m,i,x,y,s,q[100001],sol[100001],fol[100001];

void citire();
void bf();
void afisare();

int main(){
    citire();
    bf();
    afisare();
    return 0;
}

void citire(){
int i;
     freopen("bfs.in","r",stdin);
     scanf("%d %d %d",&n,&m,&s);
     for (i=1;i<=n;i++){
         a[i]=(int*)malloc(sizeof(int));
         a[i][0]=0;    
     }
     for (i=1;i<=m;i++){
         scanf("%d %d", &x,&y);
         a[x][0]++;
         a[x]=(int*) realloc(a[x],(a[x][0]+1)*sizeof(int));
         a[x][a[x][0]]=y;
     }
}

void bf(){ 
int i,j,u;
     q[0]=s;
     fol[s]=1;
     sol[s]=0;
     for (i=0,u=0;i<=u;i++){
         x=q[i];
         for (j=1;j<=a[x][0];j++)
             if (!fol[a[x][j]]){
                fol[a[x][j]]=1;
                sol[a[x][j]]=sol[x]+1;
                q[++u]=a[x][j];
             }
     }
}

void afisare(){
     freopen("bfs.out","w",stdout);
     for (i=1;i<=n;i++)
         if (fol[i])
            printf("%d ",sol[i]);
         else
             printf("-1 ");
     printf("\n");
}