#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;


vector<int> bfs(vector<vector<int>> &adj_lists, int S) {
	// initializam o coada
	// initializam un vector de vizitat
	queue<int> q;
	vector<bool> visited(adj_lists.size(), false);
	// S este nodul sursa
	// rezultat
	vector<int> res(adj_lists.size(), -1);

	// mark source node visited and enqueue it
	res[S] = 0;
	visited[S] = true;
	q.push(S);

	// cat timp nu am parcurs toate nodurile
	// trebuie sa aflam distanta de la S la fiecare nod i
	while(!q.empty()) {
		int crt = q.front();
		q.pop();

		// trb sa bag in q nodurile adiacente pt nodul crt
		for(int x : adj_lists[crt]) {
			if (!visited[x]) {
				visited[x] = true;
				res[x] = res[crt] + 1;
				q.push(x);
			}
		}
	}

	return res;

}

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

	// det nr min de arce care trebuie parcurse pt a ajunge de la nodul S la nodul X
	int a, b;
	int N, M, S, X;
	// urm M linii contin x, y cu propr ca exista arc orientat de la x la y
	// N varfuri

	// in fisierul de out vom avea distanta de la S la i (N numere)

	scanf("%d %d %d ", &N, &M, &S);
	vector <vector<int>> adj_lists(N + 1);

	for (int i = 0; i < M; i++) {
		scanf("%d %d ", &a, &b);
		adj_lists[a].push_back(b);
	}
	// am creat listele de adiacenta

	vector<int> res(N + 1);
	res = bfs(adj_lists, S);

	for(int i = 1; i < N + 1; i++) {
		cout << res[i] << " ";
	}

	return 0;
}