#include <stdio.h>
#define N 1000000
typedef struct
{
    int val,urm;
}lista;
lista v[N+1];
int ultim[N+1];
int rez[N+1];
int q[N+1];

void bfs(int s)
{
    int p=0,u=0,x,y,poz;
    q[u++] = s;//adaug s in q
    rez[s] = 0;
    while(p<u)//cat timp q nu e vida
    {
        x = q[p++];//scot x din coada
        //parcurg vecinii y ai lui x
        poz = ultim[x];
        while(poz!=-1)
        {
            y = v[poz].val;
            if(rez[y] == -1)
            {
                rez[y] = 1 + rez[x];
                q[u++] = y;
            }
            poz = v[poz].urm;
        }
    }
}

void minus1()
{
    int i;
    for(i=1;i<N;i++)
    {
        v[i].urm=-1;
        ultim[i]=-1;
        q[i]=-1;
        rez[i]=-1;
    }
    return ;
}

int main()
{
    FILE *in,*out;
    in=fopen("bfs.in","r");
    out=fopen("bfs.out","w");
    int n,m,s,i,a,b,nr=0,j;
    fscanf(in,"%d%d%d",&n,&m,&s);
    minus1();
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&a,&b);
        v[nr].val=b;
        v[nr].urm=ultim[a];
        ultim[a]=nr;
        nr++;
    }
    /*
    for(i=1 ; i<=n ; i++)
    {
        j = ultim[i];
        fprintf(out, "lista lui %d:\t",i);
        while(j!=-1)
        {
            fprintf(out,"%d ",v[j].val);
            j = v[j].urm;
        }
        fprintf(out,"\n");
    }
    */
    bfs(s);
    for(i=1;i<=n;i++)
    {
        fprintf(out,"%d ",rez[i]);
    }
    return 0;
}