#include <bits/stdc++.h>

using namespace std;

#define NMAX 100009
#define INT_MAX 2147483647

class Task {
  public:
    void solve() {
        read_input();
        print_output(get_result());
    }

  private:
    int n, m, source;
    vector<int> adj[NMAX];

    void read_input() {
        ifstream fin("bfs.in");
        fin >> n >> m >> source;

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

            adj[x].push_back(y);
        }
        fin.close();
    }

    vector<int> get_result() {
        return do_bfs();
    }

    vector<int> do_bfs() {
        vector<int> d(n + 1);
        vector<int> p(n + 1);

        bfs(source, d, p);

        return d;
    }

    void bfs(int source, vector<int> &d, vector<int> &p) {
        queue<int> Q;

        for (int i = 1; i <= n; ++i) {
            d[i] = INT_MAX;
            p[i] = -1;
        }

        Q.push(source);
        d[source] = 0;
        p[source] = 0;

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

            for (auto it : adj[node]) {
                if (d[node] + 1 < d[it]) {
                    d[it] = d[node] + 1;
                    p[it] = node;

                    Q.push(it);
                }
            }
        }
    }

    void print_output(vector<int> d) {
        ofstream fout("bfs.out");
        for (int i = 1; i < d.size(); ++i) {
            if (d[i] == INT_MAX) {
                fout << -1 << " ";
            } else {
                fout << d[i] << " ";
            }
        }
        fout << "\n";
        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}