#include <fstream>

using namespace std;

ifstream f ("bfs.in");
ofstream g ("bfs.out");

struct nod_lista
{
    int info;
    nod_lista *adr;
} *v[100005];

struct nod_coada
{
    int info;

    nod_coada *adr;

    int cost;
}*p, *u;

void adaugare_lista (int x, int y)
{
    nod_lista *c;
    c = new nod_lista;

    c -> info = y;
    c -> adr = v[x];

    v[x] = c;
}

void eliminare_lista (int x)
{
    nod_lista *p;
    p = v[x];

    v[x] = v[x] -> adr;
    delete p;
}

void adaugare_coada (int x, int cost)
{
    nod_coada *c;
    c = new nod_coada;

    c -> info = x;
    c -> cost = cost;

    c -> adr = NULL;
    u -> adr = c;

    u = c;
}

void eliminare_coada ()
{
    nod_coada *c;

    c = p;
    p = p -> adr;

    delete c;
}

int n, m, s, x, y;
int cost[100005], viz[100005];

void citire ()
{
    f >> n >> m >> s;

    u = new nod_coada;

    u -> adr = NULL;
    u -> info = s;
    u -> cost = 1;

    p = u;

    for (int i = 1; i <= m; i ++)
    {
        f >> x >> y;
        adaugare_lista (x, y);
    }

    viz[s] = 1;
}

void bfs ()
{
    int curent;

    while (p)
    {
        curent = p -> info;
        cost[curent] = p -> cost;

        while (v[curent])
        {
            if(!viz[v[curent] -> info])
            {
                adaugare_coada (v[curent] -> info, cost[curent] + 1);
                viz[v[curent] -> info] = 1;
            }

            eliminare_lista (curent);
        }

        eliminare_coada ();
    }
}

int main()
{
    citire ();

    bfs ();

    for (int i = 1; i <= n; i ++)
        g << cost[i] - 1 <<" ";

    f.close ();
    g.close ();
    return 0;
}