#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
#define ech(It, A) for (__typeof(A.begin()) It = A.begin(); It != A.end(); ++It)

const int inf = 1<<30;

int main() {
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int n, m, s;
	fin >> n >> m >> s;

	vector<int> adjl[n+1];
	for (int i = 0; i < m; ++i) {
		int u, v;
		fin >> u >> v;
		adjl[u].push_back(v);
	}

	queue<int> Q;
	Q.push(s);
	vector<int> dist(n+1, inf);
	dist[s] = 0;

	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		ech(it, adjl[u]) {
			if (dist[*it] > dist[u]+1) {
				dist[*it] = dist[u]+1;
				Q.push(*it);
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		fout << (dist[i] == inf ? -1 : dist[i]) << ' ';
	}
	fout << '\n';

	return 0;
}