#include <stdio.h>
#include <stdlib.h>
#define Max 100001

typedef struct node
{
    int info;
    struct node *next;

}nod;

nod *a[Max];
int n,m,s;
int pus[Max];
int drum[Max],x[Max];

void adNod(int x,int y)
{
    nod *q;
    nod *p;

    q = (nod *)malloc(sizeof(nod));
    q->next = NULL;
    q->info = y;

    if(a[x] == NULL)
    {
        a[x] = q;
    }
    else
    {
        p = a[x];
        while(p->next != NULL)
        p = p->next;
        p->next = q;
    }
}
void read()
{
    freopen("bfs.in","rt",stdin);
    int i,x,y;
    scanf("%d %d %d",&n,&m,&s);
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d",&x,&y);
        adNod(x,y);
    }
}
void afis()
{
    int i;
    freopen("bfs.out","wt",stdout);

    for(i = 1; i <= n; i++)
    if(drum[i] == 0)
    drum[i] = -1;
    drum[s] = 0;
    for(i = 1; i <= n; i++)
    printf("%d ",drum[i]);

}
void bf()
{
    int st,dr,sursa,k;
    nod *p;

    st = 1;
    dr = 1;
    sursa = s;
    x[1] = s;
    pus[s] = 1;
    k = 1;


    while(st <= dr)
    {
        p = a[sursa];
        while(p != NULL)
        {
            if(pus[p->info] == 0)
            {
            k++;
            x[k] = p->info;
            pus[p->info] = 1;
            drum[p->info] = drum[sursa] + 1;
            dr++;
            }
            p = p->next;
        }

        sursa = x[st+1];
        st++;

    }

}
int main()
{
    read();
    bf();
    afis();

    return 0;
}