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

typedef struct nod {
        int vf;
        struct nod* next;
} NOD, *PNOD;
PNOD l[100001];
int d[100001];
int q[100001], ql = 1;

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

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

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;
    q[1] = s;
    
    for ( k = 1; k <= m; k++ )
    {
        scanf("%d %d", &i, &j);
        Add(i, j);
    }
    BFS();
    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()
{
    i = 1;
    while ( i <= ql )
    {
          nod = q[i];
          for ( PNOD p = l[nod]; p; p = p->next )
              if ( d[p->vf] == -1 )
                 d[p->vf] = d[nod]+1,
                 ql++, q[ql] = p->vf;
          i++;
    }
}