#include <cassert>
#include <cstdio>
#include <vector>
#include <queue>

#define MAXN 100000
#define INF 0x7fffffff

struct ele {
	int to, pret;
	ele(int a, int b):to(a),pret(b) {}
	ele() = default;
};

std::vector<ele> muchii[MAXN];

bool viz[MAXN];
int drum_minim[MAXN];

struct comp {
	bool operator() (ele a, ele b) const {
		return a.pret > b.pret;
	}
};


int main () {
	int n, m;
	int start = 0;;
	int i;
	std::priority_queue<ele, std::vector<ele>, comp> q;

	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	scanf("%d%d", &n, &m);
	scanf("%d", &start); -- start;

	for (i = 0; i != m; ++ i) {
		int de, la, pret;
		scanf("%d%d", &de, &la);
		-- de, -- la;
		//scanf("%d", &pret);
		pret = 1;
		muchii[de].emplace_back(la, pret);
	}

	q.emplace(start, 0);

	while (!q.empty()) {
		int nod, p;

		{
			ele x;
			x = q.top();
			nod = x.to;
			p = x.pret;
			q.pop();
		}

		if (viz[nod] == true)
			continue;

		assert(drum_minim[nod] == p);

		viz[nod] = true;

		for (auto [to, pret] : muchii[nod]) {
			if (drum_minim[to] == 0 ||
			    p + pret < drum_minim[to]) {
				drum_minim[to] = p + pret;
				q.emplace(to, drum_minim[to]);
			}
		}
	}

	for (i = 0; i != start; ++ i) {
		if (drum_minim[i])
			printf("%d ", drum_minim[i]);
		else
			printf("-1 ");
	}

	printf("0 ");

	for (i = start + 1; i != n; ++ i)
		if (drum_minim[i])
			printf("%d ", drum_minim[i]);
		else
			printf("-1 ");
}