#include <fstream>
#include <vector>
#include <bitset>
#include <cstring>
using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int n,i,a,b,m,cv[100001],s,c[100001],p=1,u=1;
vector<int> A[100001];
bitset <100001> vi;

void bfs(int nod) {
    vector<int>::iterator it;
    int x;c[u]=nod;
    while (p<=u) {
        x=c[p];
        for (it=A[x].begin();it!=A[x].end();it++) {
            if (cv[*it]==-1) {
                cv[*it]=cv[x]+1;
                c[++u]=*it;
            }
        }
        p++;
    }
    return;
}

int main () {
    f >> n >> m >> s;
    for (i=1;i<=m;i++) {
        f >> a >> b;
        A[a].push_back(b);
    }
    memset(cv,-1,sizeof(cv));
    cv[s]=0;
    bfs(s);
    for (i=1;i<=n;i++) g << cv[i] << ' ';
    f.close();g.close();
    return 0;
}