#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 100000
#define M 1000000

typedef struct
{
    int vf, urm;
} element;

int lst[N+1], nr, n, m, s, q[N+1], d[N+1], pred[N+1];
element v[2*M+1];

void adauga(int x, int y)
{//adauga pe y in lista de adiacenta a lui x
    v[++nr].vf = y;
    v[nr].urm = lst[x];
    lst[x] = nr;
}

void push(int *pdr, int val)
{
    q[++(*pdr)] = val;
}

void pop(int *pst)
{
    ++(*pst);
}

int front(int st)
{
    return q[st];
}

bool empty(int st, int dr)
{
    return (st > dr);
}

void bfs(int x0)
{
    int st_q = 0, dr_q = -1;
    ///initializarea vectorului d
    for (int i = 1; i <= n; i++)
    {
        d[i] = -1;
    }
    d[x0] = 0;
    push(&dr_q, x0);
    while (!empty(st_q, dr_q))
    {
        int x = front(st_q);
        pop(&st_q);
        for (int p = lst[x]; p != 0; p = v[p].urm)
        {
            int y = v[p].vf;
            if (d[y] == -1)
            {
                d[y] = 1 + d[x];
                push(&dr_q, y);
            }
        }
    }
}

int main()
{
    FILE *in, *out;
    in = fopen("bfs.in", "r");
    out = fopen("bfs.out", "w");
    fscanf(in, "%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        adauga(x, y);
        //adauga(y, x);
    }
    bfs(s);
    for (int i = 1; i <= n; i++)
    {
        fprintf(out, "%d ", d[i]);
    }

    fclose(in);
    fclose(out);
    return 0;
}