#include <iostream>
#include <fstream>
#include <vector>
#include <list>

int main() {
    std::ifstream fileIn("bfs.in");
    std::ofstream fileOut("bfs.out");

    int n, m, s;

    fileIn >> n >> m >> s;

    std::vector<int> *nodes = new std::vector<int>[n + 1]();
    std::vector<int> dist(n + 1, -1);
    std::vector<bool> seen(n + 1, false);

    int a, b;
    for (int i(0); i < m; i++) {
        fileIn >> a >> b;
        nodes[a].push_back(b);
    }

    std::list<int> myQ;

    myQ.push_back(s);
    seen[s] = true;
    dist[s] = 0;

    int head;
    while (!myQ.empty()) {
        head = myQ.front();
        myQ.pop_front();
        for (int node : nodes[head]) {
            if (seen[node]) continue;
            myQ.push_back(node);
            seen[node] = true;
            dist[node] = dist[head] + 1;
        }
    }

    for (int i(1); i <= n; i++) {
        fileOut << dist[i] << ' ';
    }
    fileOut << std::endl;

    delete[] nodes;
    fileIn.close();
    fileOut.close();
    return 0;
}