#include <cstdio>
#include <cstring>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

const int V = 100000;
const int E = 1000000;

int f, b, Q[V + V], seen[V], d[V];
int ec, eb[V], en[E], et[E];

int main() {
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	memset(d, -1, sizeof d);
	memset(eb, -1, sizeof eb);
	int n = next_int();
	int m = next_int();
	int s = next_int() - 1;
	for (int i = 0; i < m; i++) {
		int u = next_int() - 1;
		int v = next_int() - 1;
		et[ec] = v;
		en[ec] = eb[u];
		eb[u] = ec++;
	}
	Q[b++] = s;
	Q[b++] = 0;
	seen[s] = true;
	while (b - f > 0) {
		int u = Q[f++];
		int c = Q[f++];
		d[u] = c;
		for (int e = eb[u]; e != -1; e = en[e]) {
			int v = et[e];
			if (seen[v] == false) {
				seen[v] = true;
				Q[b++] = v;
				Q[b++] = c + 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", d[i]);
	}
	return 0;
}