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

using namespace std;

typedef struct { int x; int y; } per;

int main(){
	int n, m, s, i, j, nv;
	vector<per> edges;
	vector<int> *v;
	deque<per> que;
	
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	scanf("%d %d %d", &n, &m, &s);
	s--;
	vector<int> ch(n, 0);
	vector<char> mark(n, 0);
	vector<int> d(n, -1);
	v = new vector<int>[n];

	edges.reserve(m);

	per p, pp;
	for (i = 0; i < m; i++){
		scanf("%d %d", &p.x, &p.y);
		p.x--;
		p.y--;
		edges.push_back(p);
		ch[p.x]++;
		ch[p.y]++;
	}

	for (i = 0; i < n; i++){
		v[i].reserve(ch[i]);
	}

	for (i = 0; i < m; i++){
		p = edges[i];
		v[p.x].push_back(p.y);
	}

	p.x = s;
	p.y = 0;
	mark[s] = 1;

	que.push_back(p);

	while (!que.empty()){
		p = que.front();
		que.pop_front();
		//printf("%d %d\n", p.x, p.y);
		d[p.x] = p.y;
		for (i = 0; i < v[p.x].size(); i++){
			nv = v[p.x][i];
			if (mark[nv] == 0){
				pp.x = nv;
				pp.y = p.y + 1;
				mark[nv] = 1;
				que.push_back(pp);
			}
		}
	}
	for (i = 0; i <= n - 1; i++) {
		printf("%d ", d[i]);
	}
	return 0;
}