#include <fstream>
#define NMAX 100002

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

struct nod{
	int vf;
	struct nod* urm;
};

typedef struct nod*  LSI;
LSI L[NMAX];
LSI p[NMAX];
bool viz[NMAX];

int n, m, start, i, nrp[NMAX];

void citire();
void bfs(int);
void ins(LSI& L, int x, LSI p);

int main(){
	citire();
	bfs(start);
	for (i = 1; i <= n; i++)
		if (nrp[i] == 0 && i != start)
			fout << -1 << ' ';
		else
			fout << nrp[i] << ' ';
	return 0;
}

void citire(){
	int x, y, i;
	fin >> n >> m;
	fin >> start;
	for (i = 1; i <= m; i++){
		fin >> x >> y;
		ins(L[x], y, p[x]);
		if (p[x] == NULL)
			p[x] = L[x];
		else
			p[x] = p[x]->urm;
	}
}

void bfs(int start){
	int C[NMAX], x, prim, ultim;
	LSI q;
	C[0] = start;
	prim = ultim = 0;
	viz[start] = 1;
	while (prim <= ultim){
		x = C[prim++];
		for (q = L[x]; q; q = q->urm)
			if (!viz[q->vf]){
				viz[q->vf] = 1;
				C[++ultim] = q->vf;
				nrp[q->vf] = nrp[x] + 1;
			}
	}
}

void ins(LSI& L, int x, LSI p){
	LSI q = new nod;
	q->vf = x;
	if (p == NULL){
		q->urm = L;
		L = q;
	}
	else{
		q->urm = p->urm;
		p->urm = q;
	}
}