#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 100010
#define M 1000100

using namespace std;

int fin[N];

struct dlist{
    int val,prev;

}lis[M];

int que[M],drum[N],head,tail;

void enq(int x){
    que[head++]=x;
}
int deq(){
    return que[tail++];
}

int main(){
    int n,m,s,x,y;
    int i;
    int endlist,cr,vec,v;

    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);

    scanf("%d%d%d",&n,&m,&s);

    for(i=1;i<=n;i++){
        fin[i]=drum[i]=-1;
    }
    endlist=0;
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        lis[endlist].val=y;
        lis[endlist].prev=fin[x];
        fin[x]=endlist++;
    }

    drum[s]=0;
    enq(s);

    while(head>tail){
        cr=deq();
        vec=fin[cr];

        do{
            v=lis[vec].val;
            if(drum[v]==-1){
                drum[v]=drum[cr]+1;
                enq(v);
            }

            vec=lis[vec].prev;
        }while(vec!=-1);

    }

    for(i=1;i<=n;i++){
        printf("%d ",drum[i]);
    }


    return 0;
}