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

int main() {
    std::ifstream fin("bfs.in");
    std::ofstream fout("bfs.out");

    const int nMax = 1e5;

    int n, m, start; fin >> n >> m >> start; start -= 1;
    std::vector<std::vector<int>> graph(n, std::vector<int>());
    for (int i = 0; i < m; i += 1) {
        int u, v; fin >> u >> v; u -= 1, v -= 1;
        graph[u].emplace_back(v);
    }

    std::vector<int> dist(n, -1); dist[start] = 0;
    std::queue<int> q; q.push(start);
    std::bitset<nMax> vis; vis[start] = true;
    while (!q.empty()) {
        int currNode = q.front(); q.pop();
        for (int& next : graph[currNode]) {
            if (vis[next] == false) {
                dist[next] = dist[currNode] + 1;
                q.push(next), vis[next] = true;
            }
        }
    }

    for (auto d : dist) {
        fout << d << ' ';
    }

    dist.clear(), graph.clear();
    fin.close(), fout.close();
    return 0;
}