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

using namespace std;

const int MAX_N = 100005;
const char FILEIN[] = "bfs.in";
const char FILEOUT[] = "bfs.out";

int n, m, start;
vector<int> graph[MAX_N];
int dmin[MAX_N];

void readGraph() {
	ifstream fin(FILEIN);
	fin >> n >> m >> start;
	for (int i = 0; i < m; ++i) {
		int a, b;
		fin >> a >> b;
		graph[a].push_back(b);
	}
}

void bfs(int start) {
	memset(dmin, -1, sizeof(dmin));
	dmin[start] = 0;

	queue<int> queue;
	queue.push(start);
	while (!queue.empty()) {
		int node = queue.front();
		queue.pop();

		for (vector<int>::iterator it = graph[node].begin(); it != graph[node].end(); ++it)
			if (dmin[*it] == -1) {
				dmin[*it] = dmin[node] + 1;
				queue.push(*it);
			}
	}
}

void printAnswer() {
	ofstream fout(FILEOUT);
	for (int i = 1; i <= n; ++i)
		fout << dmin[i] << " ";
}

int main() {
	readGraph();
	bfs(start);
	printAnswer();
}