#include <cstdio>
#include <vector>
#define NMax 100000
using namespace std;

vector<int> a[NMax+1];
int COADA[NMax+1];
int d[NMax+1];

int main(){
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);

    int i,N,M,S,inc,sf,x,y;

    scanf("%d %d %d",&N,&M,&S);
    for(i = 1; i <= M; ++i)
    {
        scanf("%d %d",&x,&y);
        a[x].push_back(y);
    }
    for(i = 1; i <= N; ++i) d[i] = -1;

    inc = sf = d[S] = 0;
    COADA[0] = S;
    while(inc <= sf)
    {
        x = COADA[inc++];
        for(i = 0; i < a[x].size(); ++i)
        if( d[ a[x][i] ] == -1 )
        {
            d[ a[x][i] ] = d[x] + 1;
            COADA[++sf] = a[x][i];
        }
    }

    for(i = 1; i <= N; ++i) printf("%d ",d[i]);


return 0;
}