#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

void dijkstra(vector<vector<int>>& edges, int start, vector<int>& dist) {
    dist.resize(edges.size(), -1);
    dist[start] = 0;
    queue<int> q; q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        // cout << node << '\n';
        q.pop();
        for (auto next : edges[node]) {
            // cout << "  " << next << '\n';
            if (dist[next] == -1) {
                dist[next] = dist[node] + 1;
                q.push(next);
            }
        }
    }
    
    // cout << dist[end] << ' ';
}

int main() {
    ifstream in("bfs.in");
    ofstream out("bfs.out");
    int n, m; in >> n >> m;
    int start; in >> start; start--;
    vector<vector<int>> edges(n);

    cerr << "linia 35\n";

    for (int i = 0; i < m; i++) {
        int a, b; in >> a >> b; a--; b--;
        edges[a].push_back(b);
    }

    cerr << "linia 42\n";

    vector<int> ans;
    dijkstra(edges, start, ans);

    cerr << "linia 47\n";
    
    for (int i = 0; i < ans.size(); i++) {
        out << ans[i] << ' ';
    }
    return 0;
}