#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define pb push_back
#define tr(c, i) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

int N;
vector< vector<int> > G;

void bfs(int S, vector<int> &D) {
	D.resize(N+1);
	fill(D.begin(), D.end(), -1);

	queue<int> Q;
	Q.push(S);
	D[S] = 0;
	
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();

		tr(G[u], v) {
			if (D[*v] == -1) {
				D[*v] = D[u] + 1;
				Q.push(*v);
			}
		}
	}
}

int main(int argc, char *argv[]) {
	int M, S, u, v;

	FILE *fi = fopen("bfs.in", "r");
	fscanf(fi, "%d %d %d", &N, &M, &S);
	G.resize(N+1);
	while (M--) {
		fscanf(fi, "%d %d", &u, &v);
		G[u].pb(v);
	}
	fclose(fi);
	
	vector<int> D;
	bfs(S, D);

	FILE *fo = fopen("bfs.out", "w");
	for (vector<int>::const_iterator ii = D.begin()+1; ii != D.end(); ++ii)
		fprintf(fo, "%d ", *ii);
	fprintf(fo, "\n");
	fclose(fo);

	return 0;
}