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

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

 int main(){
    node *p,*q;
    long long i,j,N,M,k,S,x,viz[100],cost[100];
    node *c;
    c=(node*)calloc(1,sizeof(node));
    FILE* fin,*fout;
    fin=fopen("bfs.in","r");
    fout=fopen("bfs.out","w");
    fscanf(fin,"%d %d %d",&N,&M,&S);
    
    for(k=1;k<=M;k++)
    { fscanf(fin,"%d %d",&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);
    
    codita.prim=codita.ultim=NULL;
    PushC(S);
    for(i=1;i<=N;i++) { cost[i]=0;
                        viz[i]=-1;}
      viz[S]=1;
      while(codita.prim<=codita.ultim)
      {                       c=L[codita.prim->info];
                              
                              
                                while(c)
                              {
                                 if(!viz[c->info]) 
                                 {
                                     PushC(c->info);
                                     viz[c->info]=1;
                                     cost[c->info]=cost[codita.prim->info]+1;
                                  }
                                  c=c->next;
                              }
                              PopC();
      }
      for(i=1;i<=N;i++) { if(viz[i]!=-1) fprintf(fout,"pentru nodul %d nr minim de arce este %d ",i,cost[i]);
                           else         fprintf(fout,"-1");}
  
  
  system("PAUSE");	
  return 0;
}