#include<fstream>
#include<vector>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int d[100005],c[1000005],a,b,n,m,S,p,u;
vector<int> v[100005];
int i;
char f[100005];
int main(){
    fin>>n>>m>>S;
    for(i=1;i<=n;i++){
        d[i]=-1;
    }
    d[S]=0;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b);
    }
    // BFS
    p=1;
    u=1;
    c[1]=S;
    f[S]=1;
    while(p<=u){
        for(i=0;i<v[ c[p] ].size();i++){
            if( f[ v[ c[p] ][ i ] ] == 0 ){
                f[ v[ c[p] ][ i ] ]=1;
                c[++u]=v[ c[p] ][ i ];
                d[ v[ c[p] ][ i ] ]=d[ c[p] ]+1;
            }
        }
        p++;
    }
    for(i=1;i<=n;i++){
        fout<<d[i]<<" ";
    }
    return 0;
}