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

struct nod
{int info;
nod *nod_urm;};

nod *Sfarsit, **ListaFii,*frunte,*varf;
int n,m,s,*cost;
bool *S;

void adauga(int NOD,int informatie)
{nod *aux=new nod;
aux->info=informatie;
aux->nod_urm=ListaFii[NOD];
ListaFii[NOD]=aux;}

void adauga_coada(int n)
{
if(frunte==Sfarsit)
  {
  frunte=new nod;
  frunte->info=n;
  frunte->nod_urm=Sfarsit;
  varf=frunte;
  }
else
  {
  nod *aux=new nod;
  varf->nod_urm=aux;
  aux->info=n;
  aux->nod_urm=Sfarsit;
  varf=aux;
  }
}

void pregateste()
{FILE *pin=fopen("bfs.in","r");
fscanf(pin,"%d",&n);
fscanf(pin,"%d",&m);
fscanf(pin,"%d",&s);

Sfarsit=new nod;
ListaFii=new nod*[n+1];
S=new bool[n+1];
cost=new int[n+1];
frunte=varf=Sfarsit;

memset(S,0,n+1);
memset(cost,-1,sizeof(cost)*(n+1));

cost[s]=0;
S[s]=1;

for(int i=1;i<=n;i++)
  ListaFii[i]=Sfarsit;
int a,b;
adauga_coada(s);
for (int i=1;i<=m;i++)
  {fscanf(pin,"%d",&a);
   fscanf(pin,"%d",&b);
   adauga(a,b);
  }

fclose(pin);
}

void rezolva()
{
while(frunte!=Sfarsit)
  {
  nod *aux=ListaFii[frunte->info];
  while(aux!=Sfarsit)
    {
    if(S[aux->info]==0)
      {
      S[aux->info]=1;
      cost[aux->info]=cost[frunte->info]+1;
      adauga_coada(aux->info);
      }
    aux=aux->nod_urm;
    }
  aux=frunte->nod_urm;
  delete frunte;
  frunte=aux;
  }
}

void incheie()
{
FILE *pout=fopen("bfs.out","w");
for(int i=1;i<=n;i++)
  fprintf(pout,"%d ",cost[i]);
fclose(pout);
delete Sfarsit;
delete []S;
delete []cost;}

int main()
{
pregateste();
rezolva();
incheie();
return 0;
}