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

using namespace std;

void bfs(
    int & s, vector<int> & distances,
    vector<bool> & visited, vector<vector<int>> & graph
) {
    queue<int> to_be_visited;
    to_be_visited.push(s);
    distances[s - 1] = 0;
    visited[s - 1] = true;
    
    while (!to_be_visited.empty()) {
        int node = to_be_visited.front();
        to_be_visited.pop();

        for (int neighbor: graph[node - 1]) {
            if (!visited[neighbor - 1]) {
                to_be_visited.push(neighbor);
                distances[neighbor - 1] = distances[node - 1] + 1;
                visited[neighbor - 1] = true;
            }
        }
    }
}

int main() {
    
    ifstream fin("bfs.in");
    int n, m, s;
    fin >> n >> m >> s;

    vector<vector<int> > graph(n);
    for (int i = 0; i < m; i++) {
        int node1, node2;
        fin >> node1 >> node2;
        graph[node1 - 1].push_back(node2);
    }
    fin.close();

    vector<int> distances(n, -1);
    vector<bool> visited(n, false);
    bfs(s, distances, visited, graph);

    ofstream fout("bfs.out");
    for (int i = 0; i < n; i++) {
        fout << distances[i] << " ";
    }
    fout.close();

    return 0;
}