#include <fstream>
#include <bitset>
#include <vector>
using namespace std;

const int NMAX = 100001;
typedef int el_t;

el_t q[NMAX];
el_t path[NMAX];
vector<el_t> G[NMAX];

int main()
{
	bitset<NMAX> visited;
	int N, S, m, r = 0, l = 0;
	ifstream f1("bfs.in");
	f1 >> N >> m >> S;
	do { int a, b; f1 >> a >> b; G[a].push_back(b); } while(--m);
	visited.set(q[r++] = S);
	path[S] = 1;
	while(l != r) {
		int c;
		vector<el_t>::iterator it;
		c = q[l++];
		for (it = G[c].begin(); it != G[c].end(); ++it)
			if (!visited[*it]) {
				path[q[r++] = *it] = path[c] + 1;
				visited.set(*it);
			}
	}
	freopen("bfs.out", "w", stdout);
	for (int i = 1; i <= N; ++i)
		printf("%d ", path[i] - 1);
	printf("\n");
	f1.close();
	return 0;
}