#include <fstream>
#include <iostream>
#include <list>
#include <queue>

using namespace std;

class Node {
	
public:
	list<Node *> neighbours;
	int dist;
	int id;
};


int main() {

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

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


	Node nodes[n + 1];
	for (int i = 1; i <= n; i++) 
		nodes[i].id = i;

	int dist[n + 1];
	for (int i = 0; i <= n; i++)
		dist[i] = -1;

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


	list<Node *> queue;
	dist[s] = 0;
	queue.push_front(&nodes[s]);

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

	}

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