#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
using namespace std;
int n,m,s;
int *L[NMAX], d[NMAX], Q[NMAX];



void citire()
{ int m,x,y,i;
 FILE *fin=fopen("bfs.in","r");
 fscanf(fin,"%d%d%d",&n,&m,&s);
 for (i=1;i<=n;i++) {L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0;}
 for (i=0;i<m;i++)
  {
   fscanf(fin,"%d%d",&x,&y);
   L[x][0]++;
   L[x]=(int*)realloc(L[x],(L[x][0]+1)*sizeof(int));
   L[x][L[x][0]]=y;
  }
 fclose(fin);
}

void bfs()
{ int i,x,p,u;
 for (i=1;i<=n;i++) d[i]=-1;
 d[s]=0;
 Q[0]=s; p=u=0;
 while (p<=u)
  {
   x=Q[p++];
   for (i=1;i<=L[x][0];i++)
    if (d[L[x][i]]==-1)
       {
	d[L[x][i]]=d[x]+1;
	Q[++u]=L[x][i];
       }
  }
}

void afisare()
{int i;
 FILE *fout=fopen("bfs.out","w");
 for (i=1;i<=n;i++)
  fprintf(fout,"%d ",d[i]);
 fclose(fout);
}


int main()
{
 citire();
 bfs();
 afisare();
 return 0;
}