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

#define NMAX 100009
#define INF (1 << 30)
#define NO_PARENT -1

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

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

    void read_input() {
        cin >> n >> m >> source;

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

            cin >> x >> y;
            
            adj[x].push_back(y);
            // adj[y].push_back(x);
        }
    }

    void do_dfs() {
        // vector de distante
        vector<int> dist(n + 1);

        // vector de parinti
        vector<int> p(n + 1);

        // incepe logica de dfs din nodul sursa
        dfs(source, dist, p);

        print_distances(dist);

        // show_paths(p);

    }

    void dfs(int startNode, vector<int> &dist, vector<int> &p) {
        queue<int> Q;

        for (int i = 1; i <= n; ++i) {
            dist[i] = INF;
            p[i] = NO_PARENT;
        }

        // introduc in coada radacina
        Q.push(startNode);
        
        // distanta pana la radacina este zero
        dist[startNode] = 0;

        // prin conventie, parintele radacinii este zero
        p[startNode] = 0;

        while (!Q.empty()) {
            // scot primul nod din coada
            int node = Q.front();
            Q.pop();

            // parcurg vecinii sai
            for (auto &it : adj[node]) {

                // daca gasesc un drum mai scurt decat cel actual, aleg acest drum
                if (dist[node] + 1 < dist[it]) {

                    // fac update la distanta si la parinte
                    dist[it] = dist[node] + 1;
                    p[it] = node;

                    // introduc nodul in coada
                    Q.push(it);
                }
            }
        }

        // fac -1 distantele catre nodurile ce nu au parcurse
        for (auto &it : dist) {
            if (it == INF) {
                it = -1;
            }
        }
    }

    /* 
        afiseaza distantele de la nodul sursa la fiecare nod din graf (0 - pentru source, -1 pentru noduri ce nu se afla in cc,
        distanta pentru nodurile din cc)
    */
    void print_distances(vector<int> &dist) {
        for (int i = 1; i <= n; ++i) {
            cout << dist[i] << " ";
        }
        cout << endl;
    }

    vector<int> reconstruct_path(int node, vector<int> &p) {
        
        // daca nu a fost gasit parinte pentru nodul cerut, inseamna ca face parte din alta cc
        if (p[node] == NO_PARENT) {
            // returneaza vectorul gol
            return {};
        }
        
        // vector pentru cale
        vector<int> path;
        
        // introduc destinatia in cale
        path.push_back(node);

        // cat timp nu se ajunge la parintele radacinii, se introduc parintii nodurilor in cale
        for (; node != 0; node = p[node]) {

            // intoduc parintele nodului in cale
            path.push_back(node);

        }

        reverse(path.begin(), path.end());
        return path;
    }

    // afiseaza calea cea mai scurta de la sursa la fiecare nod
    void show_paths(vector<int> &p) {
        for (int i = 1; i <= n; ++i) {
            if (i == source) {
                cout << i << ": nodul sursa/n";
                continue;
            }

            vector<int> path = reconstruct_path(i, p);

            if (path.size() == 0) {
                cout << i << ": nu s-a gasit cale catre acesta";
                continue;
            } 

            cout << i << ": ";
            for (auto &it : path) {
                cout << it << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    assert(freopen("bfs.in", "r", stdin) != NULL);
    assert(freopen("bfs.out", "w", stdout) != NULL);

    Task *task = new Task();
    task->solve();
    delete task;
}