#include <algorithm>
#define DIM 1000

using namespace std ;

int a[DIM][DIM] ;
int coada[DIM*DIM] ;
int rez[DIM] ;

int main () {
  freopen ("bfs.in","r",stdin) ;
  freopen ("bfs.out","w",stdout) ;

  int n , m  , s ;
  scanf ("%d%d%d" , &n , &m , &s) ;
  
  int x , y ;
  for (int i=1 ; i<=m ; ++i) {
    scanf ("%d%d" , &x , &y) ;
    a[x][y]=1 ;
  }
  
  for (int i=1 ; i<=n ; ++i)
    rez[i]=-1 ;
  
  int sfarsit=1 ;
  int inceput=1 ;
  coada[inceput]=s ;
  int pas ;
  rez[s]=0 ;
  
  while (inceput<=sfarsit) {
    pas=rez[coada[inceput]]+1 ;
    for (int i=1 ; i<=n ; ++i) {
      if (a[coada[inceput]][i]==1) {
        if(rez[i]==-1) {
          rez[i]=pas ;
          coada[++sfarsit]=i ;
        }
      }
    }
    inceput++ ;
  }
  
  for (int i=1 ; i<=n ; ++i)
    printf ("%d " , rez[i]) ;

  return 0;
}