#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <queue>

using namespace std;


class Graf {
	private:
		vector< vector<int> > adiacenta;
		int numarVarfuri, numarMuchii;
	public:
		Graf();
		Graf(int, int);
		~Graf();
		int citireListaOrientat(ifstream& in);
		int citireListaNeorientat(ifstream& in);
		int bf(int start);

		vector<int> rezolvare(int start);

};

Graf::Graf(int varfuri, int muchii) {
	for (int i = 0; i <= varfuri; i++) {
		this->adiacenta.push_back(vector<int>());
	}
	this->numarMuchii = muchii;
	this->numarVarfuri = varfuri;
}

Graf::~Graf(){
	//to-do
}

Graf::Graf() {
	this->numarMuchii = 0;
	this->numarMuchii = 0;

	// should not be used
}

int Graf::citireListaOrientat(ifstream& in) {
	int from, to;
	for (int i = 0; i < this->numarMuchii; i++) {
		in >> from >> to;
		this->adiacenta[from].push_back(to);
	}
	return 0;
}

int Graf::citireListaNeorientat(ifstream& in) {
	int from, to;
	for (int i = 0; i < this->numarMuchii; i++) {
		in >> from >> to;
		this->adiacenta[from].push_back(to);
		this->adiacenta[to].push_back(from);
	}
	return 0;
}

int Graf::bf(int start) {
	queue<int> coada;
	int nod;
	coada.push(start);
	bool vizitat[this -> numarVarfuri + 1];
	for (int i = 0; i <= numarVarfuri; i++) {
		vizitat[i] = false;
	}
	while (!coada.empty()) {
		nod = coada.front();
		coada.pop();
		vizitat[nod] = true;
		//do something with current node
		for(auto& vecin : adiacenta[nod]) {
			if (!vizitat[vecin]) {
				coada.push(vecin);
			}
		}
	}
	return 0;
}

vector<int> Graf::rezolvare(int start) {
	queue<int> coada;
	int nod;
	vector<int> distance(this->numarVarfuri + 1, -1);
	bool vizitat[this -> numarVarfuri + 1];
	for (int i = 0; i <= numarVarfuri; i++) {
		vizitat[i] = false;
	}


	coada.push(start);
	distance[start] = 0;
	while (!coada.empty()) {
		nod = coada.front();
		coada.pop();
		for(auto& vecin : adiacenta[nod]) {
			if (!vizitat[vecin]) {
				vizitat[nod] = true;
				coada.push(vecin);
				distance[vecin] = distance[nod] + 1;
			}
		}
	}

	return distance;
}

int main() {
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int varfuri, muchii, start;
	fin >> varfuri >> muchii >> start;
	Graf graf(varfuri, muchii);
	graf.citireListaOrientat(fin);
	vector<int> rezultat = graf.rezolvare(start);
	for (int i = 1; i <= varfuri; i++) {
		fout << rezultat[i] << " ";
	}

}