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

using namespace std ;

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

const int MAX = 1e5 + 14 ;

vector <int> Bfs (int source, int n, vector <int> *&gr) {
	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 (auto x: gr[node]) {
			if (dist [x] > dist [node] + 1) {
				dist [x] = dist [node] + 1 ; 
				q.push (x) ; 
			}
		}
	}
	for (auto &x : dist) {
		if (x == (1<<30)) {
			x = -1 ;
		}
	}
	return dist ;
}

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