#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 100010

using namespace std;

int n, m, start, g[NMAX], q[NMAX], c[NMAX];
vector<int> a[NMAX];

void read () {
	int i, x, y;
	freopen ("bfs.in", "r", stdin);
	scanf ("%d%d%d", &n, &m, &start);
	for (i=1; i<=m; ++i) {
		scanf ("%d%d", &x, &y);
		a[x].push_back(y);
	}
	for (i=1; i<=n; ++i)
		g[i] = a[i].size();
}

void bfs () {
	int i, j, l=1;
	memset (c, -1, sizeof(c));
	c[start] = 0;
	q[l] = start;
	for (i=1; i<=l; ++i)
		for (j=0; j<g[q[i]]; ++j)
			if (c[a[q[i]][j]] == -1) {
				q[++l] = a[q[i]][j];
				c[q[l]] = c[q[i]] + 1;
			}
}

void write () {
	int i;
	freopen ("bfs.out", "w", stdout);
	for (i=1; i<=n; ++i)
		printf ("%d ", c[i]);
	fclose (stdout);
}

int main () {
	read ();
	bfs ();
	write ();
	return 0;
}