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

template <class T>
class Nod
{
private:
    T data;
    Nod<T> *next;
    Nod<T> *prev;
public:
    Nod(){next=NULL;prev=NULL;};
    Nod(T &d)
    {
        data=d;
    }
    Nod( T &d , Nod<T> *n, Nod<T> *p ): data(d), next(n), prev(p){}//constructor
    Nod(Nod<T> &desirednod); // constructor de copiere nod
    void set_next(Nod<T> *gotonext); //seteaza un nod ca fiind urmatorul;
    void set_prev(Nod<T> *gotoback); //seteaza un nod ca fiind anteriorul;
    void set_NULL_next(); //seteaza nodul urmator ca fiind NULL;
    void set_NULL_prev(); //seteaza nodul anterior ca fiind NULL;
    Nod<T> *get_prev(); //trece la nodul anterior;
    Nod<T> *get_next(); //trece la nodul urmator;
    void set_data(T &d); //seteaza o valoare data de la tastatura;
    T& get_data();
    void set_data_param(T param); // seteaza o valoare data ca parametru;
    void get_info(); //afiseara valoarea;
    T return_data(); //returneaza valoarea;
};

template<class T>
Nod<T>::Nod( Nod &desirednod)
{
    data=desirednod.data;
    next=desirednod.next;
    prev=desirednod.prev;
}

template<class T>
void Nod<T>::set_next(Nod<T> *gotonext)
{
    next=gotonext;
}

template<class T>
void Nod<T>::set_prev(Nod<T> *gotoprev)
{
    prev=gotoprev;
}

template<class T>
void Nod<T>::set_NULL_next()
{
    this->next=NULL;
}

template<class T>
void Nod<T>::set_NULL_prev()
{
    this->prev=NULL;
}

template<class T>
void Nod<T>::set_data(T &d)
{
    data=d;
    //cout<<"Insert your desired value: ";
    //cin>>data;
    //return this->data;
}

template<class T>
void Nod<T>::set_data_param(T param)
{
    data=param;
}

template<class T>
T& Nod<T>::get_data()
{
    return data;
}

template<class T>
T Nod<T>::return_data()
{
    return this->data;
}

template<class T>
Nod<T>* Nod<T>::get_next()
{
    return this->next;
}

template<class T>
Nod<T>* Nod<T>::get_prev()
{
    return this->prev;
}


template <class T>
class lista
{
    private:
         Nod <T> *first;
         Nod <T> *last;
        int n;// numarul de elemente

    public:
        lista();//constructor
        lista(const lista<T> & dll);
        ~lista();//destructor
        void insert_first( T &data);//inserare la inceputul listei
        void insert_last( T &data);//adaugare la sfarsitul listei
        void insert_poz( T &data, int poz);//adaugare la o pozitie specificata
        void delete_first();//sterge obiectul de pe prima pozitie
        void delete_last();//sterge obiectul de pe ultima pozitie
        void delete_poz(int poz);//sterge obiectul de pe o pozitie data prin parametru
        void sortare();
        int count();//afiseaza dimensiunea listei
        bool isEmpty();//verifica daca lista este goala sau nu
        T& operator[](int poz);//supraincarcare pe operatorul [] pentru a returna obiectul de pe o anumita pozitie indicata

};

template <class T> lista<T>::lista()
{
    n=0;
}

template <class T> lista<T>::lista(const lista<T> &desiredlist)
{
    Nod <T> *rlist,*r;
    rlist=desiredlist.first;
    while(rlist!=NULL)
    {
        if(first==NULL)
        {
            first=new Nod<T>;
            first->set_data_param(rlist->return_data());
            first->set_NULL_next();
            first->set_NULL_prev();
            last=first;
        }
        else
        {
            r=new Nod<T>;
            r->set_data_param(rlist->return_data());
            last->set_next(r);
            r->set_prev(last);
            last=r;
        }
        last->set_NULL_next();
        rlist=rlist->get_next();
    }
}

template <class T>
lista<T>::~lista()
{
    Nod<T> *current;
    while(first!=NULL)
    {
        current=first;
        first=first->get_next();
        delete current;
    }
}

template <class T>
bool lista<T>::isEmpty()
{
    return !n;
}

template <class T>
void lista<T>::insert_first( T &e)
{
    if(isEmpty())
    {
        Nod<T> *newNode = new Nod<T>(e);
        first = newNode;
        last = newNode;
        n++;
    }
    else
    {
        Nod<T> *actualFirst = first;
        Nod<T> *newNode = new Nod<T>(e, actualFirst);
        actualFirst->get_prev() = newNode;
        first = newNode;
        n++;
    }
}

template <class T>
void lista<T>::insert_last(T &e)
{
    if(isEmpty())
    {
        Nod<T> *newNode = new Nod<T>(e);
        first = newNode;
        last = newNode;
        n++;
    }
    else
    {
        Nod<T> *actualLast = last;
        Nod<T> *newNode = new Nod<T>(e, NULL, actualLast);
        actualLast->set_next(newNode);
        last = newNode;
        n++;
    }
}

template <class T>
void lista<T>::insert_poz( T &e, int poz)
{
    if(isEmpty())
    {
        Nod<T> *newNode = new Nod<T>(e);
        first = newNode;
        last = newNode;
        n++;
    }
    else
        if( poz == 0)
            {
                Nod<T> *actualFirst = first;
                Nod<T> *newNode = new Nod<T>(e, actualFirst);
                actualFirst->get_prev() = newNode;
                newNode->get_prev() = NULL;
                first = newNode;
                n++;
            }
    else
        if( poz == n-1)
            {
                Nod<T> *actualLast = last->get_prev();
                Nod<T> *newNode = new Nod<T>(e, NULL, actualLast);
                actualLast->get_next() = newNode;
                newNode->get_next() = NULL;
                last = newNode;
                n++;
            }
        else
        {
            int k = poz;
            Nod<T> *aux, *aux1, *aux2, *newNode = new Nod<T>(e);
            aux = first;
            while(k>0)
            {
                aux1 = aux;
                aux = aux->get_next();
                k--;
            }
            newNode->set_prev(aux2);
            newNode->set_next(aux);
            aux2->set_next(newNode);
            aux->set_prev(newNode);
        }
}
template <class T>
void lista<T>::delete_first()
{
    Nod<T> *deSters = first;
    first = first->get_next();
    first->set_NULL_prev();
    delete deSters;
    n--;
}

template <class T>
void lista<T>::delete_last()
{
    Nod<T> *deSters = last;
    last = last->get_prev();
    last->set_NULL_next();
    delete deSters;
    n--;
}

template <class T>
void lista<T>::delete_poz(int poz)
{
    if(isEmpty()) return; //daca lista e vida nu facem nimic
    Nod<T> *deSters, *aux;
    if( n==1 && poz==0 )
    {
        first = first->get_next();
        last = last->get_next();
    }
    else
        if( poz==0 )
        {
            deSters = first;
            first = first->get_next();
            first->set_NULL_prev();
            delete deSters;
            n--;
            return;
        }
        else
            if( poz== n-1 )
        {
            deSters = last;
            last = last->get_prev();
            last->set_NULL_next();
            delete deSters;
            n--;
            return;
        }
        else
        {
            deSters = first;
            int k = poz;
            while(k>0)
            {
                aux = deSters;
                deSters = deSters->get_next();
                k--;
            }
            deSters->get_next()->get_prev() = aux;
            aux->set_next(deSters->get_next());
            delete deSters;
            n--;
            return;
        }
}

template <class T>
int lista<T>::count()
{
    Nod<T> *q = first;
    int cnt = 0;
    while (q!=NULL)
    {
        q = q->get_next();
        cnt++;
    }

    return cnt;
}

template <class T>
void lista<T>::sortare()
{
    Nod<T> *element = new Nod<T>;
    Nod<T> *aux = new Nod<T>;
    for(element = first; element!=NULL; element = element->get_next())
        if(element->get_data() > element->get_next()->get_data())
            {
                aux = element->get_data();
                element->set_data(element->get_next()->get_data());
                element->get_next()->set_data(aux);
            }
}

template <class T> T& lista<T>::operator [](int poz)
{
    Nod<T> *element=first;
    int i=0;
    if(poz==0)
        return first->get_data();
    else
        if(poz==n-1)
            return last->get_data();
        else
            if(poz<n-1 && poz >0)
                while(i!=poz)
                    element=element->get_next(),i++;
    return element->get_data();
}

template<class T>
class Coada
{
    lista<T> L;

public:
     Coada(); // Constructor
    ~Coada(); // Destructor
    void enqueue(T& ob); // Adaug un element in coada
    void dequeue(); // Elimin obiectul din fata
    T& front(); // Returnez o referinta catre cap
    T& back(); // Returnez o referinta catre baza
    int size(); // Returnez numarul de elemente
    //bool isEmpty() const; // Verific daca coada este vida

};

template<class T> Coada<T>::Coada ():L()
{
    //constructor
}

template<class T> Coada<T>::~Coada()
{
    //destructor
}

template<class T> void Coada<T>::enqueue( T& ob)
{
    L.insert_last(ob);
}

template<class T> void Coada<T>::dequeue()
{
    L.delete_first();
}

template<class T> T& Coada<T>::front()
{
    return L[0];
}

template<class T> T& Coada<T>::back()
{
    return L[L.count()];
}

template<class T> int Coada<T>::size()
{
    return L.count ();
}

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.enqueue(vertex);
  visited[vertex]=0;
 
  while(q.size () != 0)
  {
    element=q.front();
    for(unsigned int i=0;i<graph[element].size(); i++)
    {
      if(visited[graph[element][i]]==-1)
      {
        q.enqueue(graph[element][i]);
        visited[graph[element][i]]=visited[element]+1;
      }
    }
    q.dequeue();
  }
 
}
 
 
 
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;
 
}