#include <stdio.h>
typedef struct{
    int val,urm;
}liste;
liste a[1000001];
int coada[1000001];
int ultim[1000001],rez[100001],n,m,nod,nr;
void initializare(){
    int i;
    for(i=0;i<1000000;i++){
        a[i].urm=-1;
        ultim[i]=-1;
        rez[i]=-1;
    }
}
void citire(){
    int i,x,y;
    FILE *fin;
    fin=fopen("bfs.in","r");
    fscanf(fin,"%d%d%d",&n,&m,&nod);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d",&x,&y);
        /*
        a[nr].val=x;
        a[nr].urm=ultim[y];
        ultim[y]=nr;
        nr++;
        */
        a[nr].val=y;
        a[nr].urm=ultim[x];
        ultim[x]=nr;
        nr++;
    }
    fclose(fin);
}
void bfs(){
    int u,prim=0,x,y,poz;
    u++;
    coada[u]=nod;
    rez[nod]=0;
    while(prim<u){
        prim++;
        x=coada[prim];//scot x din coada
        //parcurg vecinii
        poz=ultim[x];
        while(poz!=-1){
            y=a[poz].val;
            if(rez[y]==-1){
                rez[y]=1+rez[x];
                u++;
                coada[u]=y;
            }
            poz=a[poz].urm;
        }
    }
}
void afisare(){
    int i;
    FILE *fout;
    fout=fopen("bfs.out","w");
    for(i=1;i<=n;i++){
        fprintf(fout,"%d ",rez[i]);
    }
    fprintf(fout,"\n");
    fclose(fout);
}
int main(){
    initializare();
    citire();
    bfs();
    afisare();
    return 0;
}