#include <bits/stdc++.h>
using namespace std;

const int kNmax = 100005;

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

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

    void read_input() {
        ifstream fin("bfs.in");
        fin >> n >> m >> source;
        for (int i = 1, x, y; i <= m; i++) {
            fin >> x >> y;
            adj[x].push_back(y);
            // adj[y].push_back(x);
        }
        fin.close();
    }

    void computeBFS (int src, vector<int> &dist, vector<int> parent) {
        // Declare queue
        queue<int> q;

        // Initialize distances and parents
        for (int i = 1; i <= n; ++i) {
            dist[i] = kNmax;
            parent[i] = -1;
        }

        // Add source to the queue
        q.push(src);
        dist[src] = 0;
        parent[src] = 0;

        // Do the BFS
        while (!q.empty()) {
            // Remove first node from queue
            int node = q.front();
            q.pop();

            // Parse the neighbours
            for (auto &it : adj[node]) {
                // Choose the shortest path
                if (dist[node] + 1 < dist[it]) {
                    dist[it] = dist[node] + 1;
                    parent[it] = node;

                    q.push(it);
                }
            }
        }

        // Put -1 in case the node is unreachable
        for (int i = 1; i <= n; ++i) {
            if (dist[i] == kNmax) {
                dist[i] = -1;
            }
        }
    }

    vector<int> get_result() {

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

        computeBFS(source, d, p);

        return d;
    }

    void print_output(vector<int> result) {
        ofstream fout("bfs.out");
        for (int i = 1; i <= n; i++) {
            fout << result[i] << (i == n ? '\n' : ' ');
        }
        fout.close();
    }
};

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