#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define in "bfs.in"
#define out "bfs.out"
#define N 100005

vector <int> LIST[N], d (N+1, -1);
queue <int> Q;

int n, m, s;

int main ()
{
	ifstream fin (in);
	fin >> n >> m >> s;
	for (int i = 0; i < m; ++i) {
		int x, y;
		fin >> x >> y;
		LIST[x].push_back (y);
	}
	fin.close();
	Q.push (s);
	d[s] = 0;
	while (Q.size()) {
		int x = Q.front();
		for (unsigned i = 0; i < LIST[x].size(); ++i)
			if (d[LIST[x][i]] == -1) {
				d[LIST[x][i]] = d[x] + 1;
				Q.push (LIST[x][i]);
			}
		Q.pop();
	}
	ofstream fout (out);
	for (int i = 1; i <= n; ++i)
		fout << d[i] << " ";
	fout.close();
	return 0;
}