#include <cstdio>
#define N 100003

using namespace std;

int n, m, s, rez[N];

struct nod
{
    int x;
    nod *urm;
} *a[N];

struct coada
{
    int nod, cost;
    coada *urm;
} *u;

void add(nod *&p, int x)
{
    nod *q = new nod;
    q -> x = x;
    q -> urm = p;
    p = q;
}

void citire()
{
    scanf ("%d %d %d ", &n, &m, &s);
    for (int i = 1; i <= m; ++ i)
    {
        int x, y;
        scanf ("%d %d ", &x, &y);
        if (x != y)
            add (a[x], y);
    }
}

void afisare()
{
    for (int i = 1; i < s; ++ i)
        if (rez[i] > 0)
            printf ("%d ", rez[i]);
        else
            printf ("-1 ");
    printf ("0 ");
    for (int i = s + 1; i <= n; ++ i)
        if (rez[i] > 0)
            printf ("%d ", rez[i]);
        else
            printf ("-1 ");
    printf ("\n");
}

void calculeaza()
{
    u = new coada;
    u -> nod = s;
    u -> cost = 0;
    u -> urm = NULL;
    for (coada *p = u; p; p = p -> urm)
    {
        for (nod *i = a[p -> nod]; i; i = i -> urm)
            if (!rez[i -> x])
            {
                coada *q = new coada;
                q -> nod = i -> x;
                q -> cost = 1 + p -> cost;
                q -> urm = NULL;
                u -> urm = q;
                u = q;
                rez[i -> x] = 1 + p -> cost;
            }
    }
}

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