# include <stdio.h>
# define dim 100010

int N,M,S,cost[dim];

int *a[dim];

struct nod
{
    int x;
    struct nod * adr;
};
typedef struct nod * Coada;
Coada p,q;

void Adaug( int val )
{
    Coada z = (Coada) malloc(sizeof(struct nod));
    z->x = val;
    z->adr = NULL;
    if( !p ) p = q = z;
        else
        {
            q->adr = z;
            q = q->adr;
        }
}

void Sterg()
{
    Coada z = p;
    p = p->adr;
    free(z);
}

void fin()
{
    int i,x,y;
    scanf("%d %d %d",&N,&M,&S);
    for( i = 1 ; i <= M ; ++i )
    {
        scanf("%d %d",&x,&y);
        if( !a[x] )
        {
            a[x] = (int *)malloc(sizeof(int));
            a[x][0] = 0;
        }
        ++a[x][0];
        a[x] = (int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
        a[x][a[x][0]] = y;
    }
}

void bfs()
{
    int t,gnod,gcost;

    memset(cost,-1,sizeof(cost));

    Adaug(S);
    cost[S] = 0;
    while( p )
    {
        gnod = p->x;
        gcost = cost[gnod];
        for( t = 1 ; t <= a[gnod][0]; ++t )
            if( cost[a[gnod][t]] == -1 )
            {
                cost[a[gnod][t]] = gcost+1;
                Adaug(a[gnod][t]);
            }
        Sterg();
    }
}

void fout()
{
    int i;
    for( i = 1 ; i <= N ; ++i )
        printf("%d ",cost[i]);
}

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    fin();
    bfs();
    fout();
    return 0;
}