#include <stdlib.h>
#include <stdio.h>
#define N 100004
FILE *f1,*rez;
int nr,m,stiva,viz[N],coada[N];

struct node { int inf;
              node *next; }*lung[N];

void adauga(node *&p,int inf)
{ node *r=(node*)malloc(sizeof(node));
    r->inf=inf;
    r->next=p;
    p=r;
}

void cit()
{int a,b,cont;
f1=fopen("parcurgere BFS.in","r");
fscanf(f1,"%d%d%d",&nr,&m,&stiva);
rez=fopen("parcurgere BFS.out","w");
for(cont=1;cont<=nr;++cont)
  viz[cont]=-1;
for(cont=1;cont<=m;++cont)
   {fscanf(f1,"%d%d",&a,&b);
    adauga(lung[a],b);}
fclose(f1); //se inchide primul fisier
}

void BFS(int stiva)
{int prim,ult,a;
prim=1;
ult=1;
node *r;
coada[1]=stiva;
viz[stiva]=0;
    do
    {a=coada[prim+1];
     for(r=lung[a];r;r=r->next)
        {if(viz[r->inf]==-1)
            {viz[r->inf]=viz[a]+1;
             coada[ult+1]=r->inf;}}
    }
    while(prim<=ult);
}

int main()
{int cont;
cit();
BFS(stiva);
for(cont=1;cont<=nr;++cont)
fprintf(rez,"%d ",viz[cont]);
fclose(rez);
return 0;
}