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

int **ListaFii,*NrFii;
int n,m,s,*cost,*coada,frunte,varf;
bool *S;

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

NrFii=new int[n+1];
S=new bool[n+1];
cost=new int[n+1];
coada=new int[n+1];
frunte=varf=1;

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

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

int a,b;
for (int i=1;i<=m;i++)
  {fscanf(pin,"%d",&a);
   fscanf(pin,"%d",&b);
   NrFii[a]++;
  }
fclose(pin);

ListaFii=new int*[n+1];

pin=fopen("bfs.in","r");
fscanf(pin,"%d",&n);
fscanf(pin,"%d",&m);
fscanf(pin,"%d",&s);

for(int i=1;i<=n;i++)
  {
  ListaFii[i]=new int[NrFii[i]+1];
  memset(ListaFii[i],0,sizeof(ListaFii[i])*(NrFii[i]+1));
  }
  
for (int i=1;i<=m;i++)
  {
  fscanf(pin,"%d",&a);
  fscanf(pin,"%d",&b);
  int aux=1;
  while(ListaFii[a][aux]!=0)
    aux++;
  ListaFii[a][aux]=b;
  }

fclose(pin);
}

void rezolva()
{
while(frunte<=varf)
  {
  int cnt=1;
  while(cnt<=NrFii[coada[frunte]])
    {
    if(S[ListaFii[coada[frunte]][cnt]]==0)
      {
      int aux=ListaFii[coada[frunte]][cnt];
      S[aux]=1;
      cost[aux]=cost[coada[frunte]]+1;
      adauga_coada(aux);
      }
    cnt++;
    }
  frunte++;
  }
}

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

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