#include <fstream>
#include <queue>
using namespace std;
const int MAX_N = 100100;
const int INF = 1 << 30;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector<int> graph[MAX_N];
queue<int> qu;
int costNode[MAX_N];
int N, M, S;

void bfs(int node);

int main() {
	fin >> N >> M >> S;
	for (int i = 1; i <= M; ++i) {
		int n1, n2;
		fin >> n1 >> n2;
		graph[n1].push_back(n2);
	}
	for (int i = 1; i <= N; ++i) {
		costNode[i] = INF;
	}
	costNode[S] = 0;
	bfs(S);
	for (int i = 1; i <= N; ++i) {
		if (costNode[i] == INF) {
			fout << -1 << ' ';
		} else {
			fout << costNode[i] << ' ';
		}
	}

}

void bfs(int node) {
	qu.push(node);
	while (!qu.empty()) {
		int v = qu.front();
		for (int i = 0; i < graph[v].size(); ++i) {
			if (costNode[v] + 1 < costNode[graph[v][i]]) {
				costNode[graph[v][i]] = costNode[v] + 1;
				qu.push(graph[v][i]);
			}
		}
		qu.pop();
	}
}