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

using namespace std;

void bfs(vector< vector<int> >& graph, vector<int>& dist, int src) {
	queue<int> q;
	dist[src] = 0;
	q.push(src);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (int& w : graph[v]) {
			if (dist[w] == -1 || dist[w] > dist[v] + 1) {
				dist[w] = dist[v] + 1;
				q.push(w);
			}
		}
	}
}

int main()
{
	ifstream cin("bfs.in");
	ofstream cout("bfs.out");
	int n, m, src;
	cin >> n >> m >> src;
	vector< vector<int> > graph(n);
	vector<int> dist(n, -1);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[--a].push_back(--b);
	}

	bfs(graph, dist, --src);

	for (int& x : dist) {
		cout << x << " ";
	}
	return 0;
}