#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int NMAX = 100000, MMAX = 1000000;
int *G[NMAX],N,M,S,deg[NMAX],x[MMAX],y[MMAX],dist[NMAX];

void readGraph() {

        freopen("bfs.in","r",stdin);

        scanf("%d%d%d",&N,&M,&S);

        --S;

        for(int i=0;i<M;++i) {
                scanf("%d%d",&x[i],&y[i]);
                --x[i], --y[i];
                deg[ x[i] ] ++;
        }

        for(int i=0;i<N;++i) {
                G[i] = (int*)calloc(deg[i] + 1,sizeof(int));
                G[i][deg[i]] = -1;
                deg[i] = 0;
        }

        for(int i=0;i<M;++i)
                G[ x[i] ][ deg[ x[i] ] ++ ] = y[i];
}

void BF() {

        int Q[NMAX],le,ri;
        bool vis[NMAX];
        
        memset(dist,-1,sizeof dist);
        memset(vis,false,sizeof vis);
        
        vis[ Q[le = ri = 0] = S ] = 1; dist[S] = 0;

        for(; le <= ri ; ++le)

                for(int *k = G[ Q[le] ]; *k  != -1; ++k)
                if(!vis[*k])
                {
                        vis[*k] = true;
                        dist[*k] = dist[ Q[le] ] + 1;
                        Q[++ri] = *k;
                }
}

void writeData() {

        freopen("bfs.out","w",stdout);

        for(int i=0;i<N;++i)
                printf("%d ",dist[i]);
}

int main() {

        readGraph();
        BF();
        writeData();
}