#include<fstream>
#include<queue>

using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
const int NMAX = 10001;
bool legs[NMAX][NMAX];
int M, S, N, lungime[NMAX],vizite[NMAX];

queue<int> coada;
//primul e nodul, al doilea e lungimea la care ajunge din s


void BFS() {

	for (int i = 1; i <= N; ++i)
		lungime[i] = -1;
	coada.push(S);
	vizite[S] = 1;
	lungime[S] = 0;
	while (!coada.empty()) {
		int v = coada.front();
		coada.pop();
		for (int i = 1; i <= N; ++i)
			if (vizite[i] == 0 && legs[v][i] == 1) {
				lungime[i] = lungime[v] + 1;
				coada.push(i);
				vizite[i] = 1;
			}
	}

}

int main() {
	fin >> N >> M >> S;
	for (int i = 0; i < M; ++i) {
		int x, y;
		fin >> x >> y;
		legs[x][y] = 1;
	}
	BFS();
	for (int i = 1; i <= N; ++i)
		fout << lungime[i] << ' ';
	fin.close();
	fout.close();
	return 0;
}