#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("bfs.in") ;
ofstream fout ("bfs.out") ;


int N, M , S ;

struct nod
{ int info ;
  nod * next ;
} ;

nod * L [100001] ;
int solutie [100001] ;
void Citire ()
{
    fin >> N >> M >> S;
    int x , y ;
    nod * p ;
    while ( fin >> x >> y )
     {
         p = new nod ;
         p->info = y;
         p->next = L[x];
         L[x] = p;
     }
}

void BFS ( nod * p )
{
    nod * Coada [100001] ;
    nod * intermed = new nod ;

    int viz [100001] = {0};

    intermed->info = p->info ;
    intermed->next = Coada [ 1 ] ;
    Coada [ 1 ] = intermed ;
    viz [ intermed->info ] = 1 ;

    solutie [Coada[1]->info] = 0;
    int pr = 1 , ul = 1 ;
    while ( pr <= ul )
      {
          while ( L[ Coada [pr]->info ] != 0 )
                {
                    if ( viz [ L[ Coada [pr]->info ]->info ] == 0 )
                     {
                         solutie [ L[ Coada [pr]->info ]->info ] = solutie [ Coada [pr]->info ] + 1;
                         viz [ L[ Coada [pr]->info ]->info ]= 1 ;
                         ++ul ;
                         intermed = new nod ;
                         intermed->info = L[ Coada [pr]->info ]->info ;
                         intermed->next = Coada [ ul ] ;
                         Coada [ ul ] = intermed ;

                     }
                    L[ Coada [pr]->info ] = L[ Coada [pr]->info ]->next ;
                }
         delete Coada [pr] ;
         ++ pr;
      }
  int i;
  for( i = 1 ; i <= N ; ++ i )
     {if ( i == S )
              continue ;
      else
        if ( solutie [ i ] == 0 )
              solutie [i] = -1;
     }
    for( i = 1 ; i <= N ; ++ i )
         fout << solutie [i] << " " ;
}
int main()
{
    Citire();
    nod * p = new nod ;
    p->info = S ;
    p->next = 0 ;
    BFS(p);
    return 0;
}