#include<stdio.h>
#define NDMX 100000

int v[NDMX],n,m,plecare;

typedef struct Nod { int info; struct Nod *next; } Nod;
Nod *G[NDMX];
int queue[NDMX],prim,ultim,cost[NDMX],v[NDMX];

void bfs(int plc)
{
Nod *p;
int x;
v[plc]=1;
queue[ultim++]=plc; 
cost[plc]=1;
for(prim=0;prim<ultim;prim++) {
    x=queue[prim];
    for(p=G[x];p;p=p->next)
        if(!v[p->info])
        {
        queue[ultim++]=p->info;
        v[p->info]=1;
        cost[p->info]=cost[x]+1;
        }
 }
}

int main()
{

int i,x,y;
FILE *intrare,*iesire;

Nod *p;
intrare=fopen("bfs.in","r");
fscanf(intrare,"%d %d %d",&n,&m,&plecare);
for(i=1;i<=m;i++)
 {
  fscanf(intrare,"%d %d",&x,&y);
  if(!(p=(Nod*)maloc(sizeof(Nod)))) 
	  return;
  p->info=y;
  p->next=G[x];
  G[x]=p;
 }
bfs(plecare);

iesire=fopen("bfs.out","w");
for(i=1;i<=n;i++)
   fprintf(iesire,"%d ",cost[i]-1);

fclose(intrare);
fclose(iesire);
return 0;
}