#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

//graf ORIENTAT
// n - nr varfuri,  m - nr muchii , s - sursa
// muchiile
// pt fiecare nod din graf, calculati distanta de la s la el  

//identificam automat ca trb BFS - pt determinarea celui mai scurt drum

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

int main() {
	
	int n, m, s;
	fin >> n >> m >> s;

	vector<vector<int>> vecini(n + 1);

	for (int i = 1; i <= m; i++) {
		int x, y;
		fin >> x >> y;

		vecini[x].push_back(y);
	}

	//avem lista de vecini pt fiecare nod, sa o si sortam crescator Just to be chilling
	for (int i = 1; i <= n; i++) {
		sort(vecini[i].begin(), vecini[i].end());
	}

	//BFS propriu zis.

	vector<bool> vizitat(n + 1, false);
	queue<int> coada;
	vector<int> distanta(n+1, -1);

	int nivel = 0;

	//primul
	coada.push(s);
	vizitat[s] = true;
	distanta[s] = 0;

	//cat timp e cv in coada
	//scoatem din coada si adaugam vecinii nevizitati pe care ii marcam ca vizitati pe loc

	while (!coada.empty()) {
		int nod_curent = coada.front();

		coada.pop();

		nivel++;
		for (auto v : vecini[nod_curent]) {
			if (!vizitat[v]) {
				vizitat[v] = true;
				coada.push(v);
				distanta[v] = distanta[nod_curent] + 1;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		fout << distanta[i] << ' ';
	}
}