#include<stdio.h>
#include<malloc.h>
#include<Windows.h>
#define NMAX 100003

int viz[NMAX],n,m,x;
FILE *inf,*outf;
typedef struct Node
{ int info; struct Node *next; }Node;
Node *G[NMAX];

typedef struct Coada
{ Node *prim; Node *ultim; }Coada;

int isEmpty(Coada *c)
{ return (c->prim!=c->ultim); } //am modificat cu != in loc de ==, ca sa returneze 1 daca e goala, si 0 daca nu e


int insereaza(Coada *&c, int x)
{
Node *p;
if(!(p=(Node*)malloc(sizeof(Node)))) return 0;
p->info=x;
p->next=NULL;
if(!c)
  {
	c = (Coada*)malloc(sizeof(Coada)); //aloc memorie cozii c
   c->prim=p;
   c->ultim=p;
  }
  else
  {
   c->ultim->next=p;
   c->ultim=p;
  }
return 1;
}


int citeste(Coada *c)
{
if(c->prim==NULL) return 0;
return c->prim->info;
}


int elimina(Coada *c)
{
Node *p;
if(c->prim==NULL) return 0;
p=c->prim;
c->prim=c->prim->next;
free(p);
}


void bfs(int a)
{
Coada *c = NULL;
Node *p;
int x;
insereaza(c,a);
viz[a]=1;
while(!isEmpty(c))
   {
    x=citeste(c);
    elimina(c);
    for(p=G[x];p;p=p->next)
        {
         if(viz[p->info]==0) 
            {
             insereaza(c,p->info);
             viz[p->info]=1+viz[x];
            }
        }
   }
}


void citire()
{int i,z,y;
Node *p;
inf=fopen("bfs.in","r");
fscanf(inf,"%d %d %d",&n,&m,&x);
for(i=1;i<=m;i++)
 {
  fscanf(inf,"%d %d",&z,&y);
  if(!(p=(Node*)malloc(sizeof(Node)))) return ;
  p->info=y;
  p->next=G[z];
  G[z]=p;
 }

}


void afisare()
{
int i;
outf=fopen("bfs.out","w");
for(i=1;i<=n;i++)
   fprintf(outf,"%d ",viz[i]-1);
}



int main()
{
citire();

bfs(x);
afisare();
fclose(inf);
fclose(outf);
system("pause");
return 0;
}