#include <iostream>
#include <fstream>

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


int N, M , S ;
int solutie [100001] ;

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

nod * L [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 )
{
    int i ;
    nod * Coada [100] ;
    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 , nr = 0 ;
    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 ; cout <<L[ Coada [pr]->info ]->info<<" ";
                         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 ;
                }
         ++pr;
      }
    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;
}