#include <bits/stdc++.h> 
using namespace std;

const int kNmax = 100005;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	int source;
	vector<int> adj[kNmax];

	void read_input() {
		ifstream fin("bfs.in");
		fin >> n >> m >> source;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
		}
		fin.close();
	}

	vector<int> get_result() {
		std::vector<bool> visited(n + 1, false);
		std::vector<int> minDistance(n + 1, INT_MAX);
		std::queue<int> nodeQueue;

		visited[source] = true;
		minDistance[source] = 0;
		nodeQueue.push(source);

		while (nodeQueue.size()) {
			int node = nodeQueue.front();
			for (int i = 0; i < adj[node].size(); i++) {
				if (!visited[adj[node][i]]) {
					minDistance[adj[node][i]] = minDistance[node] + 1;
					nodeQueue.push(adj[node][i]);
					visited[adj[node][i]] = true;
				}
			}
			nodeQueue.pop();
		}

		return minDistance;
	}

	void print_output(vector<int> result) {
		ofstream fout("bfs.out");
		for (int i = 1; i <= n; i++) {
			if (result[i] == INT_MAX) {
				result[i] = -1;
			}
			fout << result[i] << (i == n ? '\n' : ' ');
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}