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

class Graf
{

private:

	int nr_noduri;
	int nr_muchii;
	int start;
	vector<int>init;
	vector<int>fin;
	

public:

	Graf(){

		ifstream f("bfs.in");
		int x, y;
		f >> nr_noduri;
		f >> nr_muchii;
		f >> start;

		while (f >> x >> y) {

			init.push_back(x);
			fin.push_back(y);
		}

	}

	int get_nr_noduri() { return nr_noduri; }
	void set_nr_noduri(int n) { nr_noduri = n; }

	int get_nr_muchii() { return nr_muchii; }
	void set_nr_muchii(int m) { nr_muchii = m; }

	int get_start() { return start; }
	void set_start(int s) { start = s; }

	string get_muchii() {
		
		string text;

		int i;
		for (i = 0; i < nr_muchii; i++) {

			text += "\n" + to_string(init[i]) + " " + to_string(fin[i]);

		}
		
		return text;
	}


	void bfs1() {

		vector<int> vizit;
		for (int i = 0; i <= nr_noduri; i++) { vizit.push_back(-1); }

		queue<int>coada;
		int x;

		//cout << start << ", ";
		coada.push(start);
		vizit[start] = 0;

		while (!coada.empty()) {

			x = coada.front();
			coada.pop();

			for (int i = 0; i < nr_muchii; i++) {

				if (init[i] == x && vizit[fin[i]] == -1) {
					coada.push(fin[i]);

					vizit[fin[i]] = vizit[init[i]] + 1;
				}
			}
		}

		ofstream g("bfs.out");
		for (int i = 1; i <= nr_noduri; i++) {

			g << vizit[i] << " ";
		}
		g.close();
	}


	void bfs2() {

		vector<vector<int>> lista;
		lista.resize(get_nr_noduri() + 1);

		for (int i = 0; i < nr_muchii; i++) {

			lista[init[i]].push_back(fin[i]);
		}

		queue<int>coada;
		int x;

		vector<int> vizit;
		for (int i = 0; i <= nr_noduri; i++) { vizit.push_back(-1); }

		coada.push(start);
		vizit[start] = 0;

		while (!coada.empty()) {

			x = coada.front();
			coada.pop();

			for (int i = 0; i < lista[x].size(); i++) {

				if (vizit[lista[x][i]] == -1) {

					coada.push(lista[x][i]);
					vizit[lista[x][i]] = vizit[x] + 1;
				}
			}
		}

		ofstream g("bfs.out");
		for (int i = 1; i <= nr_noduri; i++) {

			g << vizit[i] << " ";
		}
		g.close();
	}


};

int main() {

	Graf* g = new Graf;

	g->bfs2();


	return 0;
}