#include <bits/stdc++.h>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
#define N 10001
int q[N];
bool a[N][N];
int r[N];
bool v[N];
int main(){
    int n,m,s,x,y,i;
    in>>n>>m>>s;
    for(i=1; i<=m; ++i)
        in>>x>>y, a[x][y]=1;
    int p=1, u=1;
    for(i=1; i<=n; ++i)
        r[i]=-1;
    q[1]=s;
    if(a[s][s])
        r[s]=0, v[s]=1;
    int c, nr=0;
    while(p<=u){
        c=q[p++];
        ++nr;
        for(i=1; i<=n; ++i)
            if(a[c][i] && !v[i]){
                v[i]=1, q[++u]=i;
                r[i]=r[c]+1;
            }
    }
    for(i=1; i<=n; ++i)
        out<<r[i]<<" ";
    return 0;
}