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

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

nod *Sfarsit, **ListaFii;
int n,m,s,*cost,*coada,frunte,varf;
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)
{coada[++varf]=n;}

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];
coada=new int[n+1];
frunte=varf=1;

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

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

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<=varf)
  {
  nod *aux=ListaFii[coada[frunte]];
  while(aux!=Sfarsit)
    {
    if(S[aux->info]==0)
      {
      S[aux->info]=1;
      cost[aux->info]=cost[coada[frunte]]+1;
      adauga_coada(aux->info);
      }
    aux=aux->nod_urm;
    }
  frunte++;
  }
}

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;
}