#include <iostream>

template <class T>
class Nod
{
private:
	T _info;
	Nod* _next;
	Nod* _prev;

public:
	Nod ();
	Nod (T info);
	Nod (const Nod& other);

	T GetInfo () const;
	Nod* GetNext () const;
	Nod* GetPrev () const;

	void SetInfo (T info);
	void SetNext (Nod* next);
	void SetPrev (Nod* prev);
};

template <class T>
class ListIterator
{
private:
	Nod<T> *_current;

public:
	ListIterator ();
	ListIterator (const ListIterator& other);

	T GetInfo () const;

	ListIterator& operator++();
	ListIterator& operator--();

	ListIterator operator++(int dummyValue);
	ListIterator operator--(int dummyValue);

	bool operator==(Nod<T>* isNULL);
	bool operator!=(Nod<T>* isNULL);

	bool operator==(const ListIterator& other);
	bool operator!=(const ListIterator& other);

	void SetInfo ( Nod<T>* nod);
};


template <class T>
class List
{
private:
	Nod<T>* _first;
	Nod<T>* _last;
	unsigned int _size;

public:
	List ();
	List (const List& other);
	~List ();

	void PushBack (T info);
	void PushFront (T info);

	void PopBack ();
	void PopFront ();

	ListIterator<T> Begin ();
	ListIterator<T> End ();
};

template <class T>
class Queue
{
private:
    List<T> *_list;
    int _size;
public:
    Queue();
    ~Queue();

    int GetSize();

    void Push(T c);
    T Front();
    void Pop();
};

#include <iostream>
using namespace std;

template <class T>
Queue<T>::Queue()
{
    _list = new List<T>();
    _size = 0;
}

template <class T>
Queue<T>::~Queue()
{
    delete _list;
}

template <class T>
int Queue<T>::GetSize()
{
    return _size;
}

template <class T>
void Queue<T>::Push(T c)
{
    ++_size;
    _list->PushBack(c);
}

template <class T>
T Queue<T>::Front()
{
    return _list->Begin().GetInfo();
}

template <class T>
void Queue<T>::Pop()
{
    if(_size <= 0)
    {
        cout << "The queue is empty";
        return ;
    }
    --_size;
    _list->PopFront();
}


template <class T>
List<T>::List () :
	_first (NULL),
	_last (NULL)
{

}

/*
 * Constructor de copiere. La orice moment in care se va face o copie
 * a unui List, se va apela aceasta functie, chiar daca operatia de
 * copiere nu se face explicit de catre voi. De exemplu:
 *
 *		void f (List a);
 *
 * In functia declarata mai sus, cand se apeleaza functia cu un obiect de
 * tip List, functia va face o copie a acelui obiect si acea copie
 * se va folosi in interiorul functiei. Compilatorul va sti ca atunci cand
 * face copia sa apeleze functia voastra scrisa mai jos.
 *
 * In aceasta metoda am acces la elementele private ale parametrului
 * "other" pentru ca este de acelasi tip de data ca si clasa care
 * implementeaza constructorul (amandoua sunt de tip List).
*/

template <class T>
List<T>::List (const List& other) :
	_size (other._size)
{
	Nod<T>* iterator = other._first;

	while (iterator != NULL) {
		PushBack (iterator->GetInfo ());

		iterator = iterator->GetNext ();
	}
}

/*
 * Destructor. Se apeleaza inainte sa se dealoce memoria unui obiect de tip
 * List. Se poate apela implicit de catre compilator in cazul dealocarii unui
 * obiect local, global sau static:
 *
 *		{ List list; }
 *
 * In cazul de mai sus, se creeaza obiectul si se distruge imediat, primul
 * pas din acest proces fiind apelarea metodei de mai jos, destructorul.
 * Acesta se mai poate apela implicit si in cazul memoriei alocate dinamic,
 * dar este necesar apelul operatorului delete:
 *
 *		List *list = new List ();
 *		delete list;
 *
 * De asemenea, se poate apela si explicit. Exista situatii in care se doreste
 * acest comportament:
 *
 *		List *list = new List ();
 *		list->~List ();
 *
 * Atentie, in cazul exemplului de mai sus nu se dealoca memoria pentru
 * obiectul list, doar se apeleaza destructorul ca pe o metoda normala.
 *
 * Pentru aceasta clasa, destructorul sterge toate obiectele de tip nod ce
 * formeaza structura de lista alocata dinamic.
 */

template <class T>
List<T>::~List ()
{
	Nod<T>* iterator = _first;

	while (iterator != NULL) {
		Nod<T>* purged = iterator;
		iterator = iterator->GetNext ();

		delete purged;
	}

	_first = _last = NULL;
}

/*
 * Metoda publica ce permite adaugarea unui nou element la finalul listei.
 *
 * Interfata metodei primeste doar un obiect de tip int, dar intern
 * se aloca memorie pentru pentru un nou obiect de tip Nod si sa se
 * formeaza legaturile spre acesta.
 *
 * In acelasi timp se pastreaza in mod coerent structura interna a clasei:
 * valorile lui _first si _last.
*/

template <class T>
void List<T>::PushBack (T info)
{
	Nod<T>* nod = new Nod<T> (info);

	if (_first == NULL) {
		_first = _last = nod;

		return ;
	}

	_last->SetNext (nod); nod->SetPrev (_last);
	_last = nod;
}

/*
 * Metoda publica ce permite adaugarea unui nou element la inceputul listei.
 *
 * Interfata metodei primeste doar un obiect de tip int, dar intern
 * se aloca memorie pentru pentru un nou obiect de tip Nod si sa se
 * formeaza legaturile spre acesta.
 *
 * In acelasi timp se pastreaza in mod coerent structura interna a clasei:
 * valorile lui _first si _last.
*/

template <class T>
void List<T>::PushFront (T info)
{
	Nod<T>* nod = new Nod<T> (info);

	if (_first == NULL) {
		_first = _last = nod;

		return ;
	}

	nod->SetNext (_first); _first->SetPrev (nod);
	_first = nod;
}

/*
 * Metoda publica ce permite stergerea ultimului element al listei.
 *
 * Intern, metoda reface legaturile dintre noduri, elibereaza memoria pentru
 * elementul sters si pastreaza coerenta structura interna a clase: valorile
 * _first si _last.
*/

template <class T>
void List<T>::PopBack ()
{
	if (_last == NULL) {
		return;
	}

	Nod<T>* purged = _last;
	Nod<T>* prev = _last->GetPrev ();

	delete purged;

	if (prev == NULL) {
		_first = _last = NULL;
		return ;
	}

	prev->SetNext (NULL);
	_last = prev;
}

/*
 * Metoda publica ce permite stergerea primului element al listei.
 *
 * Intern, metoda reface legaturile dintre noduri, elibereaza memoria pentru
 * elementul sters si pastreaza coerenta structura interna a clase: valorile
 * _first si _last.
*/

template <class T>
void List<T>::PopFront ()
{
	if (_first == NULL) {
		return ;
	}

	Nod<T>* purged = _first;
	Nod<T>* next = _first->GetNext ();

	delete purged;

	if (next == NULL) {
		_first = _last = NULL;
		return ;
	}

	next->SetPrev (NULL);
	_first = next;
}

/*
 * Metoda publica ce permite obtinerea unui obiect de tip ListIterator ce
 * pastreaza informatii despre structura interna a listei. Obiectul returnat
 * este initializat cu nodul de inceput al listei.
 *
 * A se observa ca s-a apelat functia:
 *
 * 		void SetInfo (ListIterator& listIterator, Nod* nod);
 *
 * Aceasta este o functie libera ce se gaseste in definitia clasei
 * ListIterator si este folosita pentru a seta ListIteratorul pe un anumit nod
 * intern al listei. Functia este FRIEND in clasa ListIterator, special pentru
 * a avea acces la nodul curent pe care il pastreaza ListIteratorul, informatie
 * la care in mod normal nu am avea acces extern, deoarece este definita ca
 * atribut privat in clasa.
 *
 * In corpul functiei se creeaza un obiect de tip ListIterator. Acesta este
 * returnat ulterior in exteriorul apelului metodei.
*/


/*
 * Metoda publica ce permite obtinerea unui obiect de tip ListIterator ce
 * pastreaza informatii despre structura interna a listei. Obiectul returnat
 * este initializat cu nodul de final al listei.
 *
 * A se observa ca s-a apelat functia:
 *
 * 		void SetInfo (ListIterator& listIterator, Nod* nod);
 *
 * Aceasta este o functie libera ce se gaseste in definitia clasei
 * ListIterator si este folosita pentru a seta ListIteratorul pe un anumit nod
 * intern al listei. Functia este FRIEND in clasa ListIterator, special pentru
 * a avea acces la nodul curent pe care il pastreaza ListIteratorul, informatie
 * la care in mod normal nu am avea acces extern, deoarece este definita ca
 * atribut privat in clasa.
*/

template <class T>
ListIterator<T> List<T>::End ()
{
	ListIterator<T> listIterator;

	SetInfo (listIterator, _last);

	return listIterator;
}


template <class T>
ListIterator<T>::ListIterator () :
	_current (NULL)
{

}

/*
 * Constructor de copiere. La orice moment in care se va face o copie
 * a unui ListIterator, se va apela aceasta functie, chiar daca operatia de
 * copiere nu se face explicit de catre voi. De exemplu:
 *
 *		void f (ListIterator a);
 *
 * In functia declarata mai sus, cand se apeleaza functia cu un obiect de
 * tip ListIterator, functia va face o copie a acelui obiect si acea copie
 * se va folosi in interiorul functiei. Compilatorul va sti ca atunci cand
 * face copia sa apeleze functia voastra scrisa mai jos.
 *
 * In aceasta metoda am acces la elementele private ale parametrului
 * "other" pentru ca este de acelasi tip de date ca si clasa care
 * implementeaza constructorul (amandoua sunt de tip ListIterator).
*/
template <class T>
ListIterator<T>::ListIterator (const ListIterator& other) :
	_current (other._current)
{

}

/*
 * Metoda publica ce intoarce valoarea informatiei nodului curent,
 * informatie care este la origine privata
*/
template <class T>
T ListIterator<T>::GetInfo () const
{
	return _current->GetInfo ();
}

/*
 * Supraincarcare operator++ folosit pentru trecerea la urmatorul nod din lista
 * Atentie, acest operator este operator ++ prefixat. Practic el va putea fi
 * apelat prin
 *
 *      ++ iterator;
 *
 * Operatorul ++ post-fixat este implementat mai jos.
*/
template <class T>
ListIterator<T>& ListIterator<T>::operator++ ()
{
	_current = _current->GetNext ();

	return *this;
}

/*
 * Supraincarcare operator-- folosit pentru trecerea la nodul anterior din
 * lista. Atentie, acest operator este operator -- prefixat. Practic el va
 * putea fi apelat prin
 *
 *      -- iterator;
 *
 * Operatorul ++ post-fixat este implementat mai jos.
*/
template <class T>
ListIterator<T>& ListIterator<T>::operator-- ()
{
	_current = _current->GetPrev ();

	return *this;
}

/*
 * Supraincarcare operator++ folosit pentru trecerea la nodul anterior din
 * lista. Atentie, acest operator este operator ++ post-fixat. Practic el va
 * putea fi apelat prin
 *
 *      iterator ++;
 *
 * Operatorul ++ post-fixat se supraincarca primind un atribut de tip int
 * dummy, nefolosit propriu-zis, dar necesar pentru a specifica faptul ca
 * este supraincarcat in mod post-fix.
*/
template <class T>
ListIterator<T> ListIterator<T>::operator++ (int dummyValue)
{
	ListIterator temp (*this);
	++ (*this);
	return temp;
}

/*
 * Supraincarcare operator-- folosit pentru trecerea la nodul anterior din
 * lista. Atentie, acest operator este operator -- post-fixat. Practic el va
 * putea fi apelat prin
 *
 *      iterator --;
 *
 * Operatorul -- post-fixat se supraincarca primind un atribut de tip int
 * dummy, nefolosit propriu-zis, dar necesar pentru a specifica faptul ca
 * este supraincarcat in mod post-fix.
*/
template <class T>
ListIterator<T> ListIterator<T>::operator-- (int dummyValue)
{
	ListIterator temp (*this);
	-- (*this);
	return temp;
}

/*
 * Supraincarcare operator== folosit pentru compararea iteratorului cu un
 * pointer la un obiect de tip Nod. Acest operator s-a supraincarcat doar
 * pentru a putea compara un obiect de tip ListIterator cu valoarea NULL
 * pentru a avea o forma mai eleganta de a verifica daca s-a ajuns la
 * finalul (sau inceputul) listei.
*/
template <class T>
bool ListIterator<T>::operator== (Nod<T>* isNULL)
{
	return _current == isNULL;
}

/*
 * Supraincarcare operator== folosit pentru compararea iteratorului cu un
 * alt operator. Acest operator poate fi folosit la compararea a doi iteratori
 * intre ei, eventual la compararea chiar cu obiectul obtinut de la:
 *
 *      ListIterator List::Begin ();
 *
 *  sau
 *
 *      ListIterator List::End ();
*/
template <class T>
bool ListIterator<T>::operator== (const ListIterator<T>& other)
{
	return _current == other._current;
}

/*
 * Supraincarcare operator!= folosit pentru inversa compararii de egalitate,
 * implementat mai sus prin operatorul ==. Acest operator s-a supraincarcat
 * doar pentru a putea compara un obiect de tip ListIterator cu valoarea NULL
 * pentru a avea o forma mai eleganta de a verifica daca s-a ajuns la
 * finalul (sau inceputul) listei.
*/
template <class T>
bool ListIterator<T>::operator!= (Nod<T>* isNULL)
{
	return ! ((*this) == isNULL);
}

/*
 * Supraincarcare operator!= folosit pentru inversa compararii de egalitate,
 * implementat mai sus prin operatorul ==. Acest operator poate fi folosit
 * la compararea a doi iteratori intre ei, eventual la compararea chiar cu
 * obiectul obtinut de la:
 *
 *      ListIterator List::Begin ();
 *
 *  sau
 *
 *      ListIterator List::End ();
*/
template <class T>
bool ListIterator<T>::operator!= (const ListIterator<T>& other)
{
	return ! ((*this) == other);
}

/*
 * Functie externa care atribuie obiectului de tip iterator o adresa specifica
 * unui Nod. Aceasta functie a fost declarata friend in clasa ListIterator
 * pentru a avea acces la atributele private din interiorul clasei. Cum doar
 * clasa List are initial acces la nodurile interne ale listei, informatie
 * utila se poate atribui clasei ListIterator doar din interiorul clasei List.
 *
 * Aceasta functie este folosita in interiorul metodelor Begin () si End () din
 * interiorul clasei List. A se observa ca aceasta functie poate fi apelata
 * de catre oricine, atribuind un obiect de tip Nod* de oriunde, dar informatie
 * utila se poate furniza doar din interiorul clasei List, ceea ce se si
 * intampla.
 *
 * O alta metoda de a simula functionalitatea descrisa mai sus era sa atribuim
 * clasa ListIterator ca o clasa friend in interiorul clasei ListIterator, dar
 * s-a preferat aceasta solutie pentru ca lasa acces doar la functionalitatea
 * de interes pentru clasa List, nu la tot prototipul clasei ListIterator.
*/
template <class T>
void ListIterator<T>::SetInfo (Nod<T>* nod)
{
	_current = nod;
}

template <class T>
Nod<T>::Nod () :
	_info (0,0),
	_next (NULL),
	_prev (NULL)
{

}

/*
 * Constructor cu un parametru de tip int. Acesta foloseste
 * parametrul pentru initializarea informatiei.
*/
template <class T>
Nod<T>::Nod (T info) :
	_info (info),
	_next (NULL),
	_prev (NULL)
{

}

/*
 * Constructor de copiere. La orice moment in care se va face o copie
 * a unui nod, se va apela aceasta functie, chiar daca operatia de copiere
 * nu se face explicit de catre voi. De exemplu:
 *
 *		void f (nod a);
 *
 * In functia declarata mai sus, cand se apeleaza functia cu un obiect de
 * tip nod, functia va face o copie a acelui obiect si acea copie se va folosi
 * in interiorul functiei. Compilatorul va sti ca atunci cand face copia
 * sa apeleze functia voastra scrisa mai jos.
 *
 * In aceasta metoda am acces la elementele private ale parametrului
 * "other" pentru ca este de acelasi tip de date ca si clasa care
 * implementeaza constructorul (amandoua sunt de tip nod).
*/
template <class T>
Nod<T>::Nod (const Nod<T>& other) :
	_info (other._info),
	_prev (other._prev),
	_next (other._next)
{

}

/*
 * Metoda publica ce intoarce valoarea informatiei, care este la origine
 * privata
*/
template <class T>
T Nod<T>::GetInfo () const
{
	return _info;
}

/*
 * Metoda publica ce intoarce adresa spre nodul anterior, adresa ce
 * este la origine privata
*/
template <class T>
Nod<T>* Nod<T>::GetPrev () const
{
	return _prev;
}

/*
 * Metoda publica ce intoarce adresa spre urmatorul nod, adresa ce
 * este la origine privata
*/
template <class T>
Nod<T>* Nod<T>::GetNext () const
{
	return _next;
}

/*
 * Metoda publica ce modifica valoarea informatiei, care este la origine
 * privata
*/
template <class T>
void Nod<T>::SetInfo (T info)
{
	_info = info;
}

/*
 * Metoda public pentru modificarea adresei spre urmatorul nod,
 * adresa ce este la origine privata
*/
template <class T>
void Nod<T>::SetNext (Nod<T>* next)
{
	_next = next;
}

/*
 * Metoda public pentru modificarea adresei spre urmatorul nod,
 * adresa ce este la origine privata
*/
template <class T>
void Nod<T>::SetPrev (Nod<T>* prev)
{
	_prev = prev;
}


template <class T>
ListIterator<T> List<T>::Begin ()
{
	ListIterator<T> listIterator;

	listIterator.SetInfo ( _first);

	return listIterator;
}
#include <fstream>
#include <vector>
using namespace std;


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

#define lim 100001
vector <int> G[lim];
int path[lim];

int S,N,M;


void bfs()
{
    Queue <int> q;
    int act;
    q.Push(S);
    path[S] = 0;
    act = S;

    while(q.GetSize() > 0)
    {
        act=q.Front();
        q.Pop();

        for(int i = 0; i < G[act].size(); ++i)
        {
            int it = G[act][i];
            if(path[it]==-1)
            {
                path[it]=path[act]+1;
                q.Push(it);
            }
        }
        /*for(auto it:G[act])
            if(path[it]==-1)
            {
                path[it]=path[act]+1;
                q.Push(it);
            }*/
    }

}


int main()
{
     int i,x,y;

    fin>>N>>M>>S;

    for(i=1; i<=M; i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
    }

    for(i=1; i<=N; i++)
        path[i]=-1;

    bfs();

    for(i=1; i<=N; i++)
        fout<<path[i]<<' ';

    fin.close();
    fout.close();
    return 0;
}