#include <vector>
#include <fstream>
#define MAX 100001

using namespace std;

vector<int> v[MAX];
int vizitat[MAX], coada[MAX];

int main() {
	int n, m, i, j, k, x, y, nr, s, inc , sf;

	ifstream fin("bfs.in");

	fin >> n >> m >> s;
	for (i = 0; i < m; ++i) {
		fin >> x >> y;
		v[x].push_back(y);
	}

	fin.close();
	
	memset(vizitat, -1, sizeof(vizitat));

	vizitat[s] = 0;
	coada[0] = s;
	inc = sf = 0;

	while (inc <= sf) {
		s = coada[inc++];

		for (i = 0; i < v[s].size(); ++i) {
			if (vizitat[v[s][i]] == -1) {
				vizitat[v[s][i]] = vizitat[s] + 1;
				coada[++sf] = v[s][i];
			}
		}
	}

	ofstream fout("bfs.out");
	for (i = 1; i <= n; ++i)
		fout << vizitat[i] << ' ';
	fout.close();

	return 0;
}