#include <stdio.h>

char matr[10000][10000];
int coada[10000];
int vizitat[10000];
int n;
FILE *fin;

void bf(int start){
   int li=0,ls=1;
   int i;//primul nod face parte din generatia 1
   coada[li]=start;
   //printf("%d ",coada[li]+1);
   int gen=1,lsgen=1;
   vizitat[start]=gen;
   while(li<ls){
     if(li==lsgen){
         lsgen=ls+1;
         gen++;
     }
//     printf("%d in generatia %d\n",coada[li]+1,gen);
     //adaug toti vecinii nevizitati ai lui coada[li];
     for(i=0;i<n;i++){
        if(matr[coada[li]][i]==1 && vizitat[i]==0){
           coada[ls]=i;
           vizitat[i]=gen+1;
           ls++;   
        }
     }
   li++;
   }
}

int main(){
  int m,s;
  fin=fopen("bfs.in","r");
  fscanf(fin,"%d%d%d",&n,&m,&s);
  int i,a,b;
  for(i=0;i<n;i++)vizitat[i]=0;
  for(i=0;i<m;i++){
       fscanf(fin,"%d%d",&a,&b);    
       //printf("(%d,%d) ",a,b);
       matr[a-1][b-1]=1;
   }
   fclose(fin);
 // printf("\n");
  bf(s-1);
  FILE *fout=fopen("bfs.out","w");
  for(i=0;i<n;i++)fprintf(fout,"%d ",vizitat[i]-1);
  fprintf(fout,"\n");
  fclose(fout);
return 0;
}