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

std::vector<int> a[100000];
int b[100001];
bool c[100001];

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

    int x, y;
    for (int i=0; i<m; ++i) {
        f >> x >> y;
        a[x].push_back(y);
    }

    b[s] = 1;
    c[s] = 1;
    std::vector<int> d;
    d.push_back(s);
    int t = 0;
    while (t < d.size()) {
        //std::cout << "t = " << t << " (" << d[t] << ")\n";
        for (int i=0; i<a[d[t]].size(); ++i) {
            if (!c[a[d[t]][i]]) {
                //std::cout << "\t" << a[d[t]][i] << ".dis = " << b[d[t]]+1 << "\n";
                b[a[d[t]][i]] = b[d[t]]+1;
                d.push_back(a[d[t]][i]);
                c[a[d[t]][i]] = 1;
            }
        }
        ++t;
    }

    std::ofstream r("bfs.out");
    for (int i=1; i<=n; ++i) {
        r << b[i]-1 << " ";
    }
    return 0;
}