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

class Solutuion {
 private:
    size_t N;
    size_t M;
    size_t source;
    vector<vector<size_t>> adj;
    vector<bool> visited;

 public:
    explicit Solutuion(ifstream &in) {
        in >> N >> M >> source;
        adj.resize(N + 1);
        visited.resize(N + 1, false);

        size_t node1, node2;
        for (size_t i = 1; i <= M; i++) {
            in >> node1 >> node2;

            adj[node1].push_back(node2);
        }
    }

    vector<int> solve() {
        vector<int> d(N + 1, -1);

        queue<size_t> q;
        q.push(source);

        size_t dist = 0;
        size_t next_layer = 0;
        size_t curr_layer = 1;

        while (!q.empty()) {
            size_t node = q.front();
            q.pop();

            visited[node] = true;
            d[node] = dist;

            for (auto neighbour : adj[node]) {
                if (visited[neighbour])
                    continue;
                
                q.push(neighbour);
                ++next_layer;
            }

            if (--curr_layer == 0) {
                curr_layer = next_layer;
                next_layer = 0;
                ++dist;
            }

        }

        return d;
    }
};

int main() {
    ifstream in("bfs.in");
    ofstream out("bfs.out");
    
    vector<int> solution = Solutuion(in).solve();
    copy(solution.begin() + 1, solution.end(), ostream_iterator<int>(out, " "));
    
    in.close();
    out.close();
    return 0;
}