#include <stdio.h>
#include <stdlib.h>
#define dim 100003

using namespace std;

FILE *f=fopen("bfs.in","r"), *g=fopen("bfs.out","w");

int *mat[dim],coada[6*dim];
char marc[dim];
int x,y,k,p,i,n,m,a,s;

void BF(int x)
{int i, j;

 i = j = 1;
 coada[1] = x;
 marc[x] = 0;

  while(i <= j)
 {x = coada[i];
  p = mat[x][0];


   for(k=1; k<=p; k++)
    if(marc[mat[x][k]] == -1)
    {j++; coada[j] = mat[x][k]; marc[mat[x][k]] = marc[x]+1;}

  i++;
 }

}




int main()
{

 fscanf(f,"%d%d%d",&n,&m,&s);

 for(i=1; i<=n; i++)
  {mat[i] = (int *)realloc(mat[i],sizeof(int));
   mat[i][0] = 0;
   marc[i] = -1;
   }

 for(i=1; i<=m; i++)
 {fscanf(f,"%d%d",&x,&y);
  mat[x][0]++;
  a = mat[x][0];

  mat[x] = (int *)realloc(mat[x],(a+1)*sizeof(int) );
  mat[x][a] = y;

 }



BF(s);

for(i=1; i<=n; i++)
 fprintf(g,"%d ",marc[i]);

fprintf(g,"\n");

fclose(f);
fclose(g);
return 0;
}