#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std ;

ifstream cin ("bfs.in") ;
ofstream cout ("bfs.out") ;

const int MAX = 1e5 + 14 ;

struct neigh {
	int node ; 
	neigh *nxt ;

	neigh (int a, neigh *aux) {
		node = a ; 
		nxt = aux ; 
	}
};

neigh *fpoint [MAX] ;
neigh *lpoint [MAX] ;

void init (int n) {
	for (int i = 1 ; i <= n ; ++ i) {
		fpoint [i] = NULL ; 
		lpoint [i] = NULL ; 
	}
}

void add_edge (int a, int b) {
	if (fpoint [a] == NULL) {
		fpoint [a] = lpoint [a] = new neigh (b, NULL) ; 
		return ;
	}
	lpoint [a] -> nxt = new neigh (b, NULL) ; 
	lpoint [a] = lpoint [a] -> nxt ;
}

vector <int> Bfs (int source, int n) {
	vector <int> dist (n + 1, 1 << 30) ; 
	dist [source] = 0 ; 
	queue <int> q ; 
	q.push (source) ; 
	while (!q.empty()) {
		int node = q.front() ;
		q.pop () ; 
		for (neigh *aux = fpoint [node] ; aux != NULL ; aux = aux -> nxt) {
			if (dist [aux -> node] > dist [node] + 1) {
				dist [aux -> node] = dist [node] + 1 ; 
				q.push (aux -> node) ; 
			}
		}
	}
	for (auto &x : dist) {
		if (x == (1<<30)) {
			x = -1 ;
		}
	}
	return dist ;
}

int main()
{
	int nodes , edges, sink; 
	cin >> nodes >> edges >> sink;
	while (edges --) {
		int x, y ; 
		cin >> x >> y ; 
		add_edge (x, y); 
	}
	vector <int> Solution = Bfs (sink, nodes) ; 
	for (int i = 1; i < (int)Solution.size(); i +=1) {
		cout << Solution [i] << ' ' ;
	}
	return 0 ;
}