#include <fstream>
#include <queue>
#include <list>
#include <algorithm>

#define NMAX 100001
#define INF  -1

using namespace std;

int n, m, src;
list<int> graph[NMAX];
int dist[NMAX];

void bfs()
{
	// initialization
	queue<int> q;
	fill_n(dist, n + 1, INF);
	q.push(src);
	dist[src] = 0;

	// main loop
	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (int y : graph[x]) {
			if (dist[y] == INF) {
				q.push(y);
				dist[y] = dist[x] + 1;
			}
		}
	}
}

int main()
{
	// read input
	ifstream fin("bfs.in");
	fin >> n >> m >> src;

	for (int i = 0; i < m; i++) {
		int x, y;
		fin >> x >> y;
		graph[x].push_back(y);
	}

	fin.close();

	// bfs
	bfs();

	// print output
	ofstream fout("bfs.out");
	for (int i = 1; i <= n; i++)
		fout << dist[i] << ' ';
	fout.close();

	return 0;
}