#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int INF = 1<<30;

class directed_graph {
	vector<int> *G;
	const int size;

  public:
	directed_graph(const int &size_source): size(size_source) {
		G = new vector<int>[size+1];
	}
	
	~directed_graph() {
		delete[] G;
	}

	void addEdge(const int &from, const int &to) {
		G[from].push_back(to);
	}

	vector<int> getDistance(const int &source) {
		vector<int> dist(size+1, INF);
		dist[source] = 0;
		queue<int> que; que.push(source);
		bitset<size+1> visited; visited[source] = 1;
		while (que.empty() == 0) {
			int node = que.front();
			int size = G[node].size();
			for (int i = 0; i < size; ++i) {
				if (visited[G[node][i]] == 0) {
					visited[G[node][i]] = 1;
					que.push(G[node][i]);
					dist[G[node][i]] = dist[node] + 1;
				}
			}
			que.pop();
		}
		return dist;
	}
};

int main() {
	ifstream in("bfs.in"); ofstream out("bfs.out");
	int N, M, source;
        in>>N>>M>>source;
	directed_graph G(N);
	for (int i = 0; i < M; ++i) {
		int from, to;
		in>>from>>to;
		G.addEdge(from, to);
	}

	vector<int> dist = G.getDistance(source);
	for (int i = 0; i < dist.size(); ++i) {
		if (dist[i] == INF) {
			out<<"-1 ";
		} else {
			out<<dist[i]<<" ";
		}
	}

	in.close(); out.close();
	return 0;
}