#include <stdio.h>
#include <algorithm>
#define maxn 100005
#define maxm 1000005
#define lim 2000000000
using namespace std;
int d[maxn],ind[maxn],lista[maxn];
struct muchie{int x,y;};
muchie v[maxm];
bool cmp(muchie a,muchie b){
    if(a.x<b.x)
        return true;
    if(a.x>b.x)
        return false;
    if(a.y<b.y)
        return true;
    else
        return false;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("bfs.in","r");
    fout=fopen("bfs.out","w");
    int i,j,k,n,m,s,st,dr;
    fscanf(fin,"%d%d%d",&n,&m,&s);
    for(i=1;i<=n;i++)
        d[i]=lim;
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d",&v[i].x,&v[i].y);
    }
    sort(v+1,v+m+1,cmp);
    for(i=1,j=1;i<=n&&j<=m;i++){
        if(v[j].x==i)
            ind[i]=j;
        while(v[j].x==i)
            j++;
    }
    st=1;
    dr=1;
    lista[st]=s;
    d[s]=0;
    while(st<=dr){
        k=ind[lista[st]];
        while(v[k].x==lista[st]){
            if(d[v[k].y]==lim){
                d[v[k].y]=d[lista[st]]+1;
                dr++;
                lista[dr]=v[k].y;
            }
            k++;
        }
        st++;
    }
    for(i=1;i<=n;i++){
        if(d[i]==lim)
            fprintf(fout,"-1 ");
        else
            fprintf(fout,"%d ",d[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}