#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int MAXN = 100010;

vector <int> Graf[MAXN];
int Best[MAXN];
queue <int> Q;

int main()
{
    int N, M, S, i, a, b, now;
    vector <int> :: iterator it;

    in >> N >> M >> S;
    for (i = 1; i <= M; i ++){
        in >> a >> b;
        Graf[a].push_back (b);
    }

    for (i = 1; i <= N; i ++)
        Best[i] = -1;

    Q.push (S);
    Best[S] = 0;

    while (!Q.empty ()){
        now = Q.front ();
        Q.pop ();

        for (it = Graf[now].begin (); it != Graf[now].end (); ++ it)
            if (Best[*it] == -1){
                Best[*it] = Best[now] + 1;
                Q.push (*it);
            }
    }

    for (i = 1; i <= N; i ++)
        out << Best[i] << " ";

    return 0;
}