#include <bits/stdc++.h>
#define MN 100005
using namespace std;
int N, M, S, pas[MN];
bitset <MN> viz;
typedef struct _nod
{
    int vf;
    _nod* next;
} *pnod;
pnod G[MN];
queue < int > C;

void add(int a, int b)
{
    pnod p = new _nod;
    p->vf = b;
    p->next = G[a];
    G[a] = p;
}

void citire()
{
    ifstream in("bfs.in");
    in >> N >> M >> S;
    for(int a, b; M; --M)
    {
        in >> a >> b;
        add(a, b);
    }
    in.close();
}

void bfs()
{
    pas[S] = 0;
    viz.set(S);
    C.push(S);
    while(!C.empty())
    {
        int nod = C.front();
        C.pop();
        for(pnod p = G[nod]; p; p = p->next)
            if(!viz.test(p->vf))
            {
                C.push(p->vf);
                viz.set(p->vf);
                pas[p->vf] = pas[nod] +1;
            }
    }
}

void afisare()
{
    ofstream out("bfs.out");
    for(int i = 1; i <= N; ++i)
    {
        if(!pas[i] && i != S) out << "-1 ";
        else out << pas[i] << ' ';
    }
    out.close();
}

int main()
{
    citire();
    bfs();
    afisare();
    return 0;
}