#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

vector<int> muchii[100001];
bool viz[100001];
int dist[100001];
queue<int> q;

void BFS() {
	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		for (int vecin : muchii[nod]) {
			if (!viz[vecin]) {
				q.push(vecin);
				viz[vecin] = true;
				dist[vecin] = dist[nod] + 1;
			}
		}
	}
}

int main() {
	int n, m, s;
	f >> n >> m >> s;

	for (int i = 1; i <= m; i++) {
		int x, y;
		f >> x >> y;
		muchii[x].push_back(y);
	}

	for (int i = 1; i <= n; i++)
		sort(muchii[i].begin(), muchii[i].end());

	// Inițializare distanțe cu -1
	for (int i = 1; i <= n; i++)
		dist[i] = -1;

	q.push(s);
	viz[s] = true;
	dist[s] = 0;

	BFS();

	// Afișăm distanțele
	for (int i = 1; i <= n; i++)
		g << dist[i] << " ";

	return 0;
}