#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("bfs.in");
ofstream g ("bfs.out");


const int NMAX = 100000;

int n, s;
vector <int> graf[NMAX + 1];
int d[NMAX + 1];

void citeste() {
	int m, a, b;
	f >> n >> m >> s;
	
	for (int i = 1; i <= m; i++) {
		f >> a >> b;
		graf[a].push_back(b);
	}
}

void rezolva() {
	for (int i = 1; i <= n; i++) d[i] = -1;
	d[s] = 0;
	
	queue <int> q;
	q.push(s);

	while(!q.empty()) {
		int nod = q.front();
		q.pop();

		int l = graf[nod].size();
		for (int i = 0; i < l; i++) {
			int fiu = graf[nod][i];
			if (d[fiu] != -1) continue;
			d[fiu] = d[nod] + 1;
			q.push(fiu);
		}
	}
}

void scrie() {
	for (int i = 1; i <= n; i++) g << d[i] << ' ';
	g << '\n';
}

int main() {
	citeste();
	rezolva();
	scrie();
	return 0;
}