#include <bits/stdc++.h>
#define MAXN 100000

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector<vector<int>> read(int& start) {
    int n, m;
    fin >> n >> m >> start;
    start--;
    vector<vector<int>> adj(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int iNode, jNode;
        fin >> iNode >> jNode;
        iNode--, jNode--;
        adj[iNode].push_back(jNode);
    }
    return adj;
}

int main() {
    int start, dist[MAXN];
    vector<vector<int>> adj = read(start);
    memset(dist, -1, sizeof(int) * adj.size());

    queue<int> neighbours;
    neighbours.push(start);
    dist[start] = 0;
    while (!neighbours.empty()) {
        int current = neighbours.front(); neighbours.pop();
        for (auto& neighbour: adj[current])
            if (dist[neighbour] == -1) {
                dist[neighbour] = dist[current] + 1;
                neighbours.push(neighbour);
            }
    }

    for (int i = 0; i < adj.size(); i++)
        fout << dist[i] << ' ';
    return 0;
}