#include <fstream>
#include <vector>
 
using namespace std;
 
vector <long> adiac[100001];
int sel[100001], dist[100001];
ifstream in ("bfs.in");
ofstream out ("bfs.out");
 
void read (vector <long> vec[], long m) {
    long a, b;
    for (long i = 0; i < m; i++) {
        in >> a >> b;
        vec[a].push_back(b);
    }
}
 
void BF (vector <long> vec[], long x) {
    long c[100001];
    unsigned long p = 1, u = 1, i;
    c[1] = x;
    while (p <= u) {
        sel[c[p]] = 1;
        for (i = 0; i < vec[c[p]].size(); i++)
            if (sel[vec[c[p]][i]] == 0) {
                c[++u] = vec[c[p]][i];
                sel[vec[c[p]][i]] = 1;
                dist[vec[c[p]][i]] = 1+dist[c[p]];
            }
        p++;
    }
    dist[x] = 0;
}
 
int main() {
    long n, m, s, i;
    in >> n >> m >> s;
    read (adiac, m);
    in.close();
    for (i = 1; i <=n; i++)
        dist[i] = -1;
    BF (adiac, s);
    for (i = 1; i <= n; i++)
        if(dist[i] == -1 || i == s)
            out << dist[i] << ' ';
        else
            out << ++dist[i] << ' ';
    out << '\n';
    out.close();
    return 0;
}