#include<stdio.h>
#include<string.h>

#define INPUT "bfs.in"
#define OUTPUT "bfs.out"
#define NMAX 100001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

struct Graph
{
  long val;
  Graph *next;
};

long N, M, S;
long Valid[ NMAX ], Deq[ NMAX ];
Graph *List[ NMAX ];

void readData()
{
  long Node1, Node2;
  Graph *adr;

  fscanf(fin, "%ld %ld %ld", &N, &M, &S);

  for(long i = 0; i < M; ++i)
  {
    fscanf(fin, "%ld %ld", &Node1, &Node2);

    adr = new Graph;
    adr -> val = Node2;
    adr -> next = List[ Node1 ];
    List[ Node1 ] = adr;
  }
}

void solve()
{
  memset(Valid, 0, sizeof(Valid));
  memset(Deq, 0, sizeof(Deq));

  Valid[ S ] = -1;
  Deq[ 0 ] = S;
  long pStart = 0, pFin = 0;

  Graph *adr;

  while(Deq[ pStart ] != 0)
  {
    adr = List[ Deq[ pStart ] ];
    
    while(adr != NULL)
    {
      if(Valid[ adr -> val ] == 0)
      {
        ++pFin;
        Deq[ pFin ] = adr -> val;
        Valid[ adr -> val ] = pStart + 1;
      }
      adr = adr -> next;
    }
    
    ++pStart;
  }

  for(long i = 1; i <= N; ++i)
  {
    if(Valid[ i ] == 0)
      Valid[ i ] = -1;
    else
    if(Valid[ i ] == -1)
      Valid[ i ] = 0;
    fprintf(stderr, "%ld ", Valid[ i ]);
  }
}

int main()
{
  readData();

  solve();

  fclose(fin);
  fclose(fout);

  return 0;
}