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

class Graf
{
private:
	int Nr_noduri, Nr_muchii;
	vector<vector<int>>Lista_de_adiacenta;
public:
	Graf(int, int, vector<vector<int>>);
	~Graf();
	void adauga_in_lista_de_adiacenta(int, int);
	void citire(istream& in);
	void afisare(ostream& out);
	friend istream& operator >>(istream&, Graf&);
	friend ostream& operator <<(ostream&, Graf&);
	vector<int> BFS(int);

};

Graf::Graf(int Nr_noduri = 0, int Nr_muchii = 0, vector<vector<int>>Lista_de_adiacenta = {}) {
	this->Nr_noduri = Nr_noduri;
	this->Nr_muchii = Nr_muchii;
	this->Lista_de_adiacenta.resize(Nr_noduri + 1);


	for (int i = 1; i < Lista_de_adiacenta.size();i++)
		for(int j=0;j<Lista_de_adiacenta[i].size();j++)
		    this->Lista_de_adiacenta[i].push_back(Lista_de_adiacenta[i][j]);


}

void Graf::adauga_in_lista_de_adiacenta(int nod_stang, int nod_drept) {
	this->Lista_de_adiacenta[nod_stang].push_back(nod_drept);
}

void Graf::citire(istream& in) {

	in >> Nr_noduri;
	in >> Nr_muchii;
	this->Lista_de_adiacenta.resize(Nr_noduri + 1);
	int stanga, dreapta;
	for (int i = 1; i <= Nr_muchii; i++)
	{

		cout << "Introduceti nodul st: ";
		in >> stanga;
		cout << "Introduceti nodul dr: ";
		in >> dreapta;
		adauga_in_lista_de_adiacenta(stanga, dreapta);
	}

}

void Graf::afisare(ostream& out) {

	out << Nr_noduri << " ";
	out << Nr_muchii << endl;
	for (int i = 1; i < Lista_de_adiacenta.size(); i++) {
		for (int j = 0; j <Lista_de_adiacenta[i].size(); j++)
			out << Lista_de_adiacenta[i][j] << " ";
	}
}

istream& operator>>(istream& in, Graf& g)
{
	g.citire(in);
	return in;
}
ostream& operator<<(ostream& out, Graf& g)
{
	g.afisare(out);
	return out;
}

Graf::~Graf() {
	this->Lista_de_adiacenta.clear();
	this->Nr_muchii = 0;
	this->Nr_noduri = 0;

}

vector<int> Graf::BFS(int Start_nod) {
	vector<int>Distante(this->Nr_noduri + 1,-1);
	deque<int>coada;
	coada.push_back(Start_nod);
	Distante[Start_nod] = 0;

	while (!coada.empty()) {
		int primul_nod_din_coada = coada.front();
		for (int i = 0; i < Lista_de_adiacenta[primul_nod_din_coada].size(); i++) {
			int nod_curent = Lista_de_adiacenta[primul_nod_din_coada][i];
			if (Distante[nod_curent] == -1) {
				coada.push_back(nod_curent);
				Distante[nod_curent] = Distante[primul_nod_din_coada] + 1;
			}
		}
		coada.pop_front();
	}

	return Distante;
}

int main()
{
	ifstream f_in("bfs.in");
	ofstream f_out("bfs.out");

	int Nr_noduri, Nr_muchii, Start_nod, Nod_st, Nod_dr;
	f_in >> Nr_noduri;
	f_in >> Nr_muchii;
	f_in >> Start_nod;
	vector<vector<int>>Lista_de_adiacenta(Nr_noduri+1);

	for (int i = 0; i < Nr_muchii; i++)
	{
		f_in >> Nod_st >> Nod_dr;
		Lista_de_adiacenta[Nod_st].push_back(Nod_dr);
	}

	Graf graf(Nr_noduri, Nr_muchii, Lista_de_adiacenta);
	///cout << graf<<endl;
	vector<int> Distante = graf.BFS(Start_nod);
	for (int i = 1; i < Distante.size(); i++)
		f_out << Distante[i] << " ";
	return 0;
}