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

typedef struct nod {
        int vf;
        struct nod* next;
} NOD, *PNOD;
PNOD l[100001];
int d[100001];
int v[100001];

int n, m, s;
int i, j, k;

void Add(int i, int j);
void BFS(int nod);

int main()
{
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &s);
    for (i = 1; i <= n; i++) d[i] = -1;
    d[s] = 0;
    
    for ( k = 1; k <= m; k++ )
    {
        scanf("%d %d", &i, &j);
        Add(i, j);
    }
    BFS(s);
    for (i = 1; i <= n; i++ )
        printf("%d ", d[i]);
    printf("\n");
    return 0;
}

void Add(int i, int j)
{
     PNOD q = new NOD;
     q->vf = j;
     q->next = l[i];
     l[i] = q;
}

void BFS(int nod)
{
     if ( v[nod] != 0 ) return;
     v[nod] = 1;
     PNOD q;
     for ( q = l[nod]; q; q = q->next )
         if ( d[q->vf] == -1 )
            d[q->vf] = d[nod] + 1;
     
     for ( q = l[nod]; q; q = q->next )
         BFS(q->vf);
}