// classification of edges in a depth first search tree
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <functional>
#include <queue>
using namespace std;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3f;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (y > x) x = y; }

const int NMAX = 100005;

vector<int> V[NMAX];
bool visited[NMAX];
int dist[NMAX];
int N, M, S;

int main() {
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	cin >> N >> M >> S;
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		V[x].push_back(y);
	}

	for (int i = 0; i < NMAX; i++) dist[i] = -1, visited[i] = false;

	queue<int> q;
	q.push(S);
	dist[S] = 0;
	visited[S] = true;
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		for (auto &i : V[current]) {
			if (!visited[i]) {
				visited[i] = true;
				dist[i] = dist[current] + 1;
				q.push(i);
			}
		}
	}

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