#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 100000
#define M 1000000

using namespace std;

int fin[N];

struct dlist{
    int val,prev;

}lis[M];

int que[N],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();

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

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


    return 0;
}