#include <iostream>

using namespace std;

int n;

struct nod
{
    int info;
    nod *adr;
} *L[1000010],*Q,*u;

void add(nod *&p,int ce)
{
    nod *q=new nod;
    q->info=ce;
    q->adr=p;
    p=q;
}

void addQ(int x)
{
    if(!Q)
    {
        Q=new nod;
        u=Q;
    }
    else
    {
        u->adr=new nod;
        u=u->adr;
    }
    u->info=x;
    u->adr=NULL;
}

int delQ()
{
    nod *back=Q;
    Q=Q->adr;
    int x=back->info;
    delete back;
    return x;
}

int pasi[1000010],s;

void lee()
{
    addQ(s);
    int x;
    memset(pasi,-1,sizeof(pasi));
    pasi[s]=0;
    while(Q)
    {
        x=delQ();
        for(nod *j=L[x];j;j=j->adr)
            if(pasi[j->info]==-1)
            {
                addQ(j->info);
                pasi[j->info]=pasi[x]+1;
            }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",pasi[i]);
    printf("\n");
}



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

    int m,x,y;
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        add(L[x],y);

    }
    /*
    printf("Listele:");
    for(int i=1;i<=m;i++)
    {
        printf("\nLista lui %d\n",i);
        for(nod *j=L[i];j;j=j->adr)
            printf("%d ",j->info);
    }
    */
    lee();
    return 0;
}