#include <fstream>
#include <vector>
#include <deque>
#include <iostream>

#define NMax 100001
#define pb push_back

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int n, m, k;
vector<int> V[NMax];
int len[NMax];
deque<int> q;

void init() {
	for (int i=1;i<=n;i++)
		len[i] = -1;
	len[k] = 0;
//	cout<<len[5]<<endl;
}

void read() {
	f>>n>>m>>k;
	for (int i=1;i<=m;i++) {
		int x, y;
		f>>x>>y;
//		cout <<x<<' '<<y<<endl;
		V[x].pb(y);
	}
}

void solve() {
	q.pb(k);

	while (!q.empty()) {
		int node = q[0];
		q.pop_front();
		
		for (int i=0;i<V[node].size();i++) {
			if (len[V[node][i]] == -1) {
//				cout<<i<<endl;
				len[V[node][i]] = len[node]+1;
				q.pb(V[node][i]);
			}
		}		
	}
}

void output() {
	for (int i=1;i<n;i++)
		g<<len[i]<<' ';
	g<<len[n]<<'\n';
}

int main() {

	read();
	init();
	solve();
	output();

	f.close(); g.close();
	return 0;
}