#include<bits/stdc++.h>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
vector<int> L[1<<17];
int v[1<<17],c[1<<17],i,n,p,u,s,x,y,m;
int main()
{
    f>>n>>m>>s;
    for(i=1;i<=m;++i)
        f>>x>>y,L[x].push_back(y);
    c[1]=s,v[s]=1,p=1,u=1;
    while(p<=u) {
        for(auto a:L[c[p]])
            if(!v[a])
                ++u,c[u]=a,v[a]=v[c[p]]+1;
        ++p;
    }
    for(i=1;i<=n;++i)
        g<<v[i]-1<<' ';
    return 0;
}