#include <bits/stdc++.h>
#define mmx -2000000000
#define ct 1000000

std::vector<int> v[100000];

std::priority_queue< std::pair<int,int> > h;

int best[100000];

char BUFF[ct];

FILE*fi;

int r=0;

int cit(){
    int nr=0;
    while(BUFF[r]<'0' || BUFF[r]>'9'){
        r++;
        if(r==ct)
        {
            r=0;
            fread(BUFF,1,ct,fi);
        }
    }
    while(BUFF[r]>='0' && BUFF[r]<='9'){
        nr=nr*10+BUFF[r]-'0';
        r++;
        if(r==ct)
        {
            r=0;
            fread(BUFF,1,ct,fi);
        }
    }
    return nr;
}

void reset(){
    for(int i=0;i<100000;i++)
        best[i]=mmx;
}

int main()
{
    int s,n,m,i,a,b,nod,val,nod2,val2;
    FILE*fo;
    fi=fopen("bfs.in","r");
    fo=fopen("bfs.out","w");
    fread(BUFF,1,ct,fi);
    n=cit();
    m=cit();
    s=cit();
    for(i=0;i<m;i++){
        a=cit();
        b=cit();
        a--;
        b--;
        v[a].push_back(b);
    }
    reset();
    s--;
    best[s]=0;
    h.push({0,s});
    while(h.empty()!=1){
        nod=h.top().second;
        val=h.top().first;
        h.pop();
        if(best[nod]==val){
            for(i=0;i<v[nod].size();i++){
                nod2=v[nod][i];
                val2=val-1;
                if(best[nod2]<val2){
                    best[nod2]=val2;
                    h.push({val2,nod2});
                }
            }
        }
    }
    for(i=0;i<n;i++){
        if(best[i]==mmx)
            fprintf(fo,"-1 ");
        else fprintf(fo,"%d ",-best[i]);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}