#include <iostream>
#include<vector>
#include<fstream>
using namespace std;

template<class ListType> class Lista
{
private:
  struct Nod
  {
    Nod *next;
    Nod *back;
    ListType info;
  };
  Nod *front_;
  Nod *end_;
  int list_size;

public:
  Lista();//*
  // ~Lista();//*
   void adauga_inceput(ListType x);//*
   void push(ListType x);//*
   void adauga_pe_poz(int pozitie,ListType x);//*
   void pop();//*
   void sterge_sfarsit();//*
   void sterge_dupa_poz(int pozitie);//*
   int getSize();//*
  // void afisare();//*
   ListType &operator[](int i);//*
   bool is_empty();//*
   void sort_();//*

};

template <class ListType> Lista<ListType>::Lista()
{
  list_size=0;
}

//template <class ListType> Lista<ListType>::~Lista()
//{
//for(int i=0; i<list_size; i++)
//{
//Nod *aux=front_;
//front_=aux->next;
//front_->back=NULL;
//delete aux;
//}
//}

template <class ListType>ListType &Lista<ListType> ::operator[](int i)
{
  Nod *aux;
  aux=front_;
  for(int k=0; k<i; k++)
       aux=aux->next;

  return aux->info;
}

template <class ListType>void Lista<ListType>::push(ListType x)
{
  if(list_size==0)
  {
    Nod*p=new Nod;
    p->info=x;
    p->back=NULL;
    p->next=NULL;
    front_=p;
    end_=front_;
  }

  else
  {

    Nod*p=new Nod;
    p->info=x;
    p->back=end_;
    p->next=NULL;
    end_->next=p;
    end_=p;

  }
  list_size=list_size+1;
}

template <class ListType>int Lista<ListType>::getSize()
{
  return list_size;
}

template <class ListType>void Lista<ListType>::adauga_inceput(ListType x)
{
  if(list_size==0)
  {
    Nod*p=new Nod;
    p->info=x;
    p->back=NULL;
    p->next=NULL;
    front_=p;
    end_=front_;
  }

  else
  {

    Nod*p=new Nod;
    p->info=x;
    p->back=NULL;
    p->next=front_;
    front_=p;
  }

  list_size=list_size+1;
}

template <class ListType>void Lista<ListType>::adauga_pe_poz(int pozitie,ListType x)
{
  if((list_size==0) || (pozitie==0))
    adauga_inceput(x);
  else
  {
    Nod *aux1=new Nod;
    aux1->info=x;
    Nod *aux2;
    aux2=front_->next;

    for(int j=1; j<=pozitie; j++)
    {
      aux2=aux2->next;
    }
    aux1->next=aux2;
    aux1->back=aux2->back;
    aux2->back->next=aux1;
    aux2->back=aux1;
    list_size=list_size+1;
  }

}


//template <class ListType>void Lista<ListType>::afisare()
//{
// Nod *c;
//c=front_;
// while(c!=end_)
// {
//cout<<c->info<<" ";
// c=c->next;
// }
//}


template <class ListType> void Lista <ListType> :: sterge_dupa_poz(int pozitie)
{

  if (pozitie==0 || list_size==0)
  {
    pop();

  }
  else if(pozitie==list_size-1)
  {
    sterge_sfarsit();

  }
  else
  {
    Nod *aux;
    aux=front_;
    for(int i=0; i<pozitie; i++)
      aux=aux->next;
    aux->back->next=aux->next;
    aux->next->back=aux->back;
    delete aux;

    list_size=list_size-1;
  }
}



template <class ListType> void Lista<ListType>::sort_()
{
  Nod *aux1=new Nod;
  Nod *aux2=new Nod;
  Nod *copie=new Nod;

  for(aux1=front_; aux1!=end_->back; aux1=aux1->next)
  {
    for(aux2=aux1->next; aux2!=end_; aux2=aux2->next)
    {
      if(aux2->info<aux1->info)
      {
        copie->info=aux1->info;
        aux1->info=aux2->info;
        aux2->info=copie->info;

      }
    }
  }
}

template <class ListType>void Lista <ListType> :: pop()
{cout<<"A";
  if(list_size>1)
  {
    Nod*q=front_;
    front_->back=NULL;
    front_=front_->next;
    delete q;
    list_size--;
  }
  else {

    Nod  *aux=front_;
    front_=end_=NULL;
    list_size=0;
    delete aux;
  }

cout<<"A";
}

template <class ListType>void Lista <ListType> :: sterge_sfarsit()
{
  if(list_size>0)
  {
    Nod*q=end_;
    end_->back->next=NULL;
    end_=end_->back;
    delete q;
    list_size--;
  }
  else cout<<"Lista vida !\n";
}

template<class ListType>bool Lista<ListType>::is_empty()
{
  if(list_size==0)
    return true;

   return false;
}


template <class QueueType> class Coada //: virtual public Lista<QueueType>
{
private :
          Lista <QueueType> C;


public :
  void push(QueueType x);//*
  void pop();//*
  QueueType get_front();//*
  bool is_empty();//*

};



template <class QueueType> void Coada<QueueType> :: push(QueueType x)
{
  C.push(x);
}

template <class QueueType> void Coada<QueueType> :: pop()
{
  C.pop();

}

template <class QueueType> QueueType Coada<QueueType> :: get_front()
{
  return C[0];
}



template <class QueueType> bool Coada<QueueType> :: is_empty()
{
  return C.is_empty();
}


int n,m,sursa;

vector < vector <int> >graph;
vector<int>visited;

void BFS(int vertex)
{
  if((vertex<0)||(vertex>n-1))
  {
    return;
  }
  Coada <int> q;
  int element;
  q.push(vertex);
  visited[vertex]=0;

  while(!q.is_empty())
  {
    element=q.get_front();
    for(unsigned int i=0;i<graph[element].size(); i++)
    {
      if(visited[graph[element][i]]==-1)
      {
        q.push(graph[element][i]);
        visited[graph[element][i]]=visited[element]+1;
      }
    }
    q.pop();
  }

}



int main()
{
int x,y;
  ifstream in("bfs.in");
  ofstream out("bfs.out");
  in>>n>>m>>sursa;
  sursa--;
  graph.resize(n);
  visited.resize(n,-1);

  for(int i=0; i<m; i++)

  {
    in>>x>>y;
    x=x-1;
    y=y-1;
    graph[x].push_back(y);
  }


  BFS(sursa);
  for(int j=0; j<n; j++)
  {
    out<<visited[j]<<" ";
  }
  return 0;

}