#include <stdio.h>
#include <stdlib.h>
#define dim 10000

int v[dim],c[dim],t[dim],a[dim][dim],tfirst,tlast;
int n,m,s;

void ini()
{
    int i;
    for (i=0;i<dim;i++)
        c[i]=-1;
}

void bfs(start)
{
    int i;
    tfirst = 0; tlast = 1;
    c[start]=0;//cost 0
    t[tfirst]=start; // put him in the tail
    while (tlast>tfirst) //still have values in tail
    {
        v[t[tfirst]] = 1; //mark as done
        for (i=1;i<=a[0][t[tfirst]];i++)
            if (v[a[i][t[tfirst]]]==0) // not done
            {
                c[a[i][t[tfirst]]]=c[t[tfirst]]+1; // calculate cost
                t[tlast] = a[i][t[tfirst]]; // add in tail
                tlast++;
            }
        tfirst ++;
    }
}

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n,&m,&s);
    int i,x1,x2;
    for (i=0;i<m;i++)
    {
        scanf("%d %d",&x1,&x2);
        a[0][x1-1]++;
        a[a[0][x1-1]][x1-1]=x2-1;
    }
    ini();
    bfs(s-1);
    for (i=0;i<n;i++)
        printf("%d ",c[i]);
    return 0;
}