#include<cstdio>
#include<queue>
#include<vector>
#define NMAX 100005
using namespace std;

vector<int> G[NMAX];
int Dist[NMAX];

int main() {
	int n, m, s;
	queue<int> Q;
	
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	
	scanf("%d%d%d", &n, &m, &s);
	for(int i = 0; i < m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
	}
	
	for(int i = 1; i <= n; ++i)
		Dist[i] = -1;
	Dist[s] = 0;
	Q.push(s);
	
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		for(int i = 0; i < (int)G[x].size(); ++i) {
			int y = G[x][i];
			if(Dist[y] == -1) {
				Dist[y] = Dist[x] + 1;
				Q.push(y);
			}
		}
	}
	
	for(int i = 1; i < n; ++i)
		printf("%d ", Dist[i]);
	printf("%d\n", Dist[n]);
	
	return 0;
}