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

void BF(int nr_varf);

/*initializam variabilele globale */

#define MAX_VF 100000
#define MAX_ARC 1000000

int viz[MAX_VF], coada[MAX_VF], distanta[MAX_VF], T[2][MAX_ARC], N, indice_coada, ultim_coada, start[MAX_VF];

void BF(int nr_varf)
{
    int i;
    if (indice_coada<=ultim_coada)
    {
        int x=start[nr_varf-1];
        while (x>0)
        {
            viz[T[0][x-1]]=1;
            coada[ultim_coada]=T[0][x-1];
            distanta[T[0][x-1]]=distanta[nr_varf]+1;
            ultim_coada++;
            x=start[T[1][x-1]];
        }
    indice_coada++;
    BF(coada[indice_coada]);
    }
}


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

    int i, x, y, Start, M;

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

    if (M>MAX_ARC)
        return 1;

    //  Citesc arcele si retin graful sub forma de lista de vecini
    int k=0;
    for (i = 1; i <= M; i++)
    {
        distanta[i]=0;
        scanf("%d %d ", &x, &y);
		T[0][k]=y;
		T[1][k]=start[x];
		start[x]=k;
		k++;
    }

    BF(Start);

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

    return 0;
}