///Nrx imi va datora un suc
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100005;

vector<int> g[NMAX];
int         d[NMAX];

int main(void) {
    FILE *fi = fopen("bfs.in", "r");
    FILE *fo = fopen("bfs.out", "w");
    int n, m, s, u, v;
    queue<int> q;

    fscanf(fi,"%d%d%d",&n,&m,&s);
    for(int i=1; i<=m; ++i) {
        fscanf(fi,"%d %d",&u,&v);
        g[u].push_back(v);
    }

    q.push(s);
    d[s] = 1;

    while(!q.empty()) {
        u = q.front();
        q.pop();

        for(auto v:g[u])
            if(!d[v])
                d[v] = d[u] + 1,
                q.push(v);
    }

    for(int i=1; i<=n; ++i)
        fprintf(fo,"%d ",--d[i]);
    fprintf(fo,"\n");

    fclose(fi);
    fclose(fo);
    return 0;
}