#include <fstream>
#include <vector>

using namespace std;

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

int main()
{
	int n, m, s, v1, v2, *v, *m1, *m2;
	vector<int> *g;
	fin >> n >> m >> s;
	v = new int[n + 1];
	g = new vector<int>[n + 1];
	m1 = new int[m];
	m2 = new int[m];
	for (int i = 1; i <= n; ++i) {
		v[i] = -1;
	}
	while (m--) {
		fin >> v1 >> v2;
		g[v1].push_back(v2);
	}
	v[s] = 0;
	m1[0] = s;
	for (int size1 = 1, size2 = 0, *aux; size1 > 0; aux = m1, m1 = m2, m2 = aux, size1 = size2, size2 = 0) {
		for (int i = 0; i < size1; ++i) {
			int node = m1[i];
			for (int j = 0; j < g[node].size(); ++j) {
				int node2 = g[node][j];
				if (v[node2] == -1) {
					v[node2] = v[node] + 1;
					m2[size2++] = node2;
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		fout << v[i] << " ";
	}
}