#include <stdio.h>
#include <stdlib.h>

typedef struct lista
{
    int nod;
    struct lista *next;
} *lista;

typedef struct coada
{
    int inf;
    struct coada *next;
} *coada;
coada prim,ultim;
lista l[100105];

int ok[100105]; //e initializat cu 0
int n,m,s;

void citire()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n,&m,&s);

    int i,x,y;
    lista nou;
    for (i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        nou=calloc(1,sizeof(lista));
        nou->nod=y;
        nou->next=l[x];
        l[x]=nou;

    }

}

void afisare()
{
    int i;
    for (i=1; i<=n; i++)
    {
        printf("%d :  ",i);
        lista p;
        p=l[i];
        while (p)
        {
            printf("%d, ",p->nod);
            p=p->next;
        }
        printf("\n");
    }
}

pune_in_coada(int nod)
{
    coada nou;
    nou=calloc(1,sizeof(coada));
    nou->inf=nod;
    nou->next=NULL;

    if (nod==s)
       {
           prim=nou;
           ultim=prim;
       }
       else
       {
           ultim->next=nou;
           ultim=nou;
       }
}

scoate_din_coada()
{
    coada aux;

    aux=prim;
    prim=prim->next;
    if (ultim==prim)
        ultim=NULL;

    free(aux);
}

void afisare_coada()
{
    coada aux;
    aux=prim;

    while (aux)
    {
        printf("%d ",aux->inf);
        aux=aux->next;
    }
    printf("\n");
}


void bfs()
{
    while (prim!=NULL)
    {
        lista p;
        p=l[prim->inf];
        while (p)
        {


            if (ok[p->nod]==0)
               {
                   ok[p->nod]=ok[prim->inf]+1;
                   pune_in_coada(p->nod);
               }
            p=p->next;
            //printf("@%d@ ",p->nod);
            //afisare_coada();
            //getch();
        }

        scoate_din_coada();
    }
}

void afisare_rezultat()
{
    int i;
    for (i=1; i<=n; i++)
        {
            printf("%d ",ok[i]);
        }
}


int main()
{
    citire();
    //afisare();
    //printf("\n\n");
    pune_in_coada(s);
    ok[s]=1;

    bfs();

    afisare_rezultat();

    return 0;
}