#include <cstdio>
#include <queue>
using namespace std;

struct nod {
	int val;
	nod *adr;
};
nod *v[100002];
int dist[100003];
int n,m,s;
queue <int> q;

void insert(int a,int b) {
	if (v[a] == NULL) {
		v[a] = new nod;
		v[a]->val = b;
		v[a]->adr = NULL;
	} else {
		nod *nou = new nod;
		nou->val = b;
		nou->adr = v[a];
		v[a] = nou;
	}
}

int main() {
	freopen("bfs.in","r",stdin);
	freopen("freopen.out","w",stdout);
	scanf("%d %d %d",&n,&m,&s);
	dist[s] = 1;
	for (int i=1;i<=n;i++) v[i] = NULL;
	for (int i=1;i<=m;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		insert(a,b);
	}
	q.push(s);
	while (!q.empty()) {
		int crt = q.front(); q.pop();
		nod *nd = v[crt];
		nod *var = nd;
		while (var!= NULL) {
			if (dist[var->val] == 0) {
				dist[var->val] = dist[crt] +1;
				q.push(var->val);
			}
			var = var->adr;
		}
	}
	for (int i=1;i<=n;i++) {
		printf("%d ",dist[i]-1);
	}
	return 0;
}