#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int main(){
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	int N, M, S;
	scanf("%d %d %d ", &N, &M, &S);
	vector<vector<int> > vecini(N + 1);
	vector<bool> visited(N + 1, false);
	queue<int> Q;
	vector<int> cost(N + 1, -1);
	for(int i = 0; i < M; i++){
		int X, Y;
		scanf("%d %d ", &X, &Y);
		vecini[X].push_back(Y);
	}
	Q.push(S);
	cost[S] = 0;
	visited[S] = true;
	while(!Q.empty()){
		int current = Q.front();
		Q.pop();
		for(int i = 0; i < vecini[current].size(); i++)
			if(!visited[vecini[current][i]]){
				Q.push(vecini[current][i]);
				visited[vecini[current][i]] = true;
				cost[vecini[current][i]] = cost[current] + 1;
			}
	}
	for(int i = 1; i <= N; i++)
		printf("%d ", cost[i]);

	return 0;
}