#include<fstream>
#include<vector>
#include<deque>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
const int NMAX = 100005;
int n, m, s;
vector<int>v[NMAX], drum(NMAX, -1);
void adiacenta() {
	int i, j;
	fin >> n >> m >> s;
	while (m--) {
		fin >> i >> j;
		v[i].push_back(j);
	}
}
void BFS() {
	int nod = s, i;
	deque<int>d;
	d.push_back(nod);
	drum[nod] = 0;
	while (!d.empty()) {
		nod = d.front();
		d.pop_front();
		for (i = 0; i<v[nod].size(); ++i)
			if (drum[v[nod][i]] == -1) {
				d.push_back(v[nod][i]);
				drum[v[nod][i]] = drum[nod] + 1;
			}
	}
}
void afisare() {
	int i;
	for (i = 1; i <= n; ++i)
		fout << drum[i] << ' ';
}
int main() {
	adiacenta();
	BFS();
	afisare();
}