#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define FOR(i,x,n) \
	for(int i = x;i <= n;i++)
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int * v[100001], n, m, s, noduri[100001];

void read() {
	f >> n >> m >> s;
	int* grad = new int[n];
	FOR(i, 1, n)grad[i] = 0;
	FOR(i, 1, m) {
		f >> grad[0];
		grad[grad[0]]++;
		f >> grad[0];
	}
	//FOR(i, 1, n)cout << grad[i] << " ";
	FOR(i, 1, n) { 
			v[i] = new int[grad[i] + 1];
			v[i][0] = 0;
			noduri[i] = -1;
	}
	delete[] grad;
	f.close();
	f.open("bfs.in");
	f >> n >> m >> s;
	FOR(i, 1, m) {
		int x, y;
		f >> x >> y;
		v[x][++v[x][0]] = y;
	}

}

void solve() {
	queue<int> que;
	que.push(s);
	noduri[s] = 0;
	while (!que.empty()) {
		FOR(i, 1, v[que.front()][0]) 
			if (noduri[v[que.front()][i]] == -1) {
				que.push(v[que.front()][i]);
				noduri[v[que.front()][i]] = noduri[que.front()] + 1;
			}
				que.pop();

		}
		FOR(i, 1, n)g << noduri[i] << ' ';

	}



int main()
{
	read();
	solve();
	//cout << endl;
	//system("pause");
    return 0;
}