#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <set>
#include <queue>

#define LUNG_MAX 500000

using namespace std;

typedef struct graph {
	vector<set<pair<int, int> > > lists;
	int nrNoduri;
	int nrMuchii;
	bool *vizitat;
	int *tata;
	int *cost_minim;
}*Graph;

Graph initGraph(int nrNoduri, int nrMuchii) {
	Graph graf = (Graph) malloc(sizeof(struct graph));
	graf->nrNoduri = nrNoduri;
	graf->nrMuchii = nrMuchii;
	graf->vizitat = (bool*) calloc(nrNoduri,sizeof(bool));
	graf->tata = (int*) malloc(nrNoduri*sizeof(int));
	graf->cost_minim = (int*) malloc(nrNoduri*sizeof(int));
	for(int i = 0; i < nrNoduri; i++) {
		graf->vizitat[i] = false;
		graf->tata[i] = -1;
		graf->cost_minim[i] = -1;
		set<pair<int, int> > lista;
		graf->lists.push_back(lista);
	}
	return graf;
}

Graph addEdge(Graph graf, int u, int v, int cost) {
	graf->lists[u].insert(make_pair(v, cost));
	return graf;
}

set<pair<int, int> > getList(Graph graf, int u) {
	return graf->lists[u];
}

Graph bfs(Graph graf, int source) {
	queue<int> coada;
	int i, j;
	set<pair<int, int> > lista;
	coada.push(source);
	graf->vizitat[source] = true;
	graf->cost_minim[source] = 0;
	while(!coada.empty()) {
		int u = coada.front();
		coada.pop();
		lista = getList(graf, u);
		for (std::set<pair<int, int> >::iterator it=lista.begin(); it!=lista.end(); ++it) {
			pair<int, int> p = *it;
			int v = p.first;
			if(graf->vizitat[v] == false) {
				coada.push(v);
				graf->vizitat[v] = true;
				graf->cost_minim[v] = graf->cost_minim[u] + 1;
			}
		}	
	}
	return graf;
}

int main() {
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	int N, M, S, i, u, v;
	scanf("%d %d %d", &N, &M, &S);
	Graph graf = initGraph(N+1, M);
	for(i = 0; i < M; i++) {
		scanf("%d %d", &u, &v);
		graf = addEdge(graf, u, v, 1);
	}
	graf = bfs(graf, S);
	for(int i = 1; i <= N; i++) {
		printf("%d ", graf->cost_minim[i]);
	}
	return 0;
}