#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;

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

        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);
        d[source] = 0;

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


        int dist = 1;
        int prev_children = 1;
        int next_children = 0;

        while(!q.empty()) {
            int curr_node = q.front();
            q.pop();

            for (auto neigh : adj[curr_node]) {
                if (d[neigh] != -1)
                    continue;
                
                d[neigh] = dist;
                next_children++;
                q.push(neigh);
            }
            
            if (--prev_children == 0) {
                prev_children = next_children;
                next_children = 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;
}