#include<stdio.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;

Coada *q;
int isEmpty(Coada *q)
{ return (q->prim==q->ultim); }


int insereaza(Coada *c, int x)
{
Node *p;
if(!(p=(Node*)malloc(sizeof(Node)))) return 0;
p->info=x;
p->next=NULL;
if(c->ultim==NULL)
  {
   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)
{

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


void citire()
{Node *p;
inf=fopen("bfs.in","r");
int i,z,y;
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;
 }
 fclose(inf);
}


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