#include <stdio.h>
#include <stdlib.h>
typedef struct node{
        int info;
        struct node *next;
        } node;
node *L[100001];

typedef struct coada { node *prim; node *ultim;} coada;
coada codita;

void PushC(int x)
{
  node *p;
   if(!(p=(node*)calloc(1,sizeof(node)))) 
     {printf("eroare memorie");
     return ;}
   p->info=x;
   p->next=NULL;
   if(codita.ultim==NULL) 
      {codita.prim=p; 
       codita.ultim=p;}
   else
       {codita.ultim->next=p;
        codita.ultim=p;}

}

void PopC()
{
if(codita.prim==NULL) 
{printf("eroare-coada vida\n");
return;}
node *p;
p=codita.prim;
codita.prim=codita.prim->next;
free(p);
}
long long viz[100001],i,j,N,M,k,S,x,cost[100001];
 int main(){
    node *p;
    node *c;
    FILE* fin,*fout;
    fin=fopen("bfs.in","r");
    fout=fopen("bfs.out","w");
    fscanf(fin,"%lld %lld %lld",&N,&M,&S);
    
    
    for(k=1;k<=M;k++)
    { fscanf(fin,"%lld %lld",&i,&j);
    p=(node*)calloc(1,sizeof(node));  //se adauga j in lista vecinilor lui i 
    p->info=j;
    p->next=L[i];
    L[i]=p;
    }
    fclose(fin);
    
    for(i=1;i<=N;i++)  cost[i]=-1;
    codita.prim=codita.ultim=NULL;
    PushC(S);
    long long cost_ant;
    viz[S]=1;cost[S]=0;
      while(codita.prim!=NULL)
      {        c=L[codita.prim->info];
               cost_ant=cost[codita.prim->info];
                while(c)
                              {
                                 if(viz[c->info]==0) 
                                 {
                                     PushC(c->info);
                                     viz[c->info]=1;
                                     cost[c->info]=cost_ant+1;
                                  }
                                  c=c->next;
                              }
               PopC();
      }
      for(i=1;i<=N;i++)  fprintf(fout,"%lld ",cost[i]);
      fclose(fout);
      return 0;
}