#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>

int n, m, s;

struct Con {
	int b, a;
};

bool vis[100008];
Con con[1000008];
int idx[100008];
int nxt[100008];
int dpt[100008];

int compare(const void * a, const void * b) {
	return(((Con *)a)->a - ((Con *)b)->a);
}

int main() {
	FILE * in = fopen("bfs.in", "rt");
	FILE * out = fopen("bfs.out", "wt");

	fscanf(in, "%d%d%d", &n, &m, &s);
	for (int i = 0; i < m; ++i) {
		fscanf(in, "%d%d", &con[i].a, &con[i].b);
		if (con[i].a == con[i].b) {
			--i;
			--m;
		}
	}

	qsort(con, m, sizeof(Con), compare);

	int k = 0;
	for (int i = 0; i < m; ++i) {
		if (k != con[i].a) {
			k = con[i].a;
			idx[k] = i;
		}
	}

	for (int i = 1; i <= n; ++i) {
		dpt[i] = -1;
	}

	int l = 0, r = 0;
	nxt[r++] = s;
	vis[s] = 1;
	dpt[s] = 0;

	while (l <= r) {
		int ta = nxt[l];
		for (int i = idx[ta]; con[i].a == ta; ++i) {
			int tb = con[i].b;
			if (!vis[tb]) {
				vis[tb] = 1;
				nxt[r++] = tb;
				dpt[tb] = dpt[ta] + 1;
			}
		}
		++l;
	}

	for (int i = 1; i <= n; ++i) {
		fprintf(out, "%d ", dpt[i]);
	}

	fclose(in);
	fclose(out);
}