#include <fstream>
#include <list>
#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define MAXN 100001
vector<int> nodes[MAXN];

int dist[MAXN];

int main() {

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

	int n, m, s;
	scanf("%d %d %d", &n, &m, &s);


	memset(dist, -1, sizeof(dist));
	
	for (int i = 0; i < m; i++) {	
		int source, dest;
		scanf("%d %d", &source, &dest);
		nodes[source].push_back(dest);
	}


	list<int> queue;
	dist[s] = 0;
	queue.push_front(s);

	while (!queue.empty()) {
		int head = queue.front(); queue.pop_front();
		vector<int>::iterator it;
		for (it = nodes[head].begin(); it != nodes[head].end(); it++) {
			if (dist[*it] == -1){
				dist[*it] = dist[head] + 1;
				queue.push_back(*it);
			}
		}

	}

	for (int i = 1; i < n; i++ ) {
		printf("%d ", dist[i]);
	}
	printf("%d", dist[n]);
}