#include <stdio.h>

struct nod
{
int x;
nod *urm;
};
struct zoro
{
int x,c;
zoro *urma;
};
typedef nod *lista;
typedef zoro *coada;
coada que,ultim;
lista A[100001];
int B[100001];

void add(int x,int c)
{
if (que==NULL)
        {
        coada urm;
        urm = new zoro;
        urm->x = x;
        urm->c = c;
        urm->urma =NULL;
        que = urm;
        ultim = que;
        }
else {
        coada urm;
        urm = new zoro;
        urm->x = x;
        urm->c = c;
        urm->urma =NULL;
        ultim->urma = urm;
        ultim = urm;
     }
}

void bfs(int p,int c)
{
B[p] = c;
lista E=A[p];
while (E!=NULL)
{
if (B[E->x]==-1 || B[E->x]>c+1) add(E->x,c+1);
E = E->urm;
}
if (que!=NULL)
        {
         int q = que->x;
         int w = que->c;
         que = que->urma;
         bfs(q,w);
        }
}

int main()
{
FILE *in=fopen("bfs.in","r");
FILE *out=fopen("bfs.out","w");

int n,m,k;

fscanf(in,"%d%d%d",&n,&m,&k);

lista urm;int x,y;

for (;m;m--)
{
fscanf(in,"%d%d",&x,&y);
urm = new nod;
urm->x = y;
urm->urm = A[x];
A[x] = urm;
}

int i;
for (i=0;i<=n;i++) B[i] = -1;


bfs(k,0);
for (i=1;i<=n;i++) fprintf(out,"%d ",B[i]);


}