#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define infile "bfs.in"
#define outfile "bfs.out"

#define NMAX 100002
int m, n;

vector<int> adj[NMAX];
int arcs[NMAX];

void bfs(int source) {

	queue<int> q;

	for (int i = 1; i <= n; i++) arcs[i] = -1;

	q.push(source);
	arcs[source] = 0;

	while (!q.empty()) {
		int node = q.front();
		q.pop();
		vector<int>::iterator it = adj[node].begin();
		for (; it != adj[node].end(); it++) {
			if (arcs[*it] == -1) {
				arcs[*it] = arcs[node] + 1;
				q.push(*it);
			} else if (arcs[*it] > arcs[node] + 1)
				arcs[*it] = arcs[node] + 1;

		}
	}

}


int main() {

	int s, a, b;

	ifstream in(infile);
	ofstream out(outfile);

	in >> n >> m >> s;

	for (int i = 0; i < m; i++) {
		in >> a >> b;
		adj[a].push_back(b);
	}

	bfs(s);

	for (int i = 1; i <= n; i++)
		out << arcs[i] << " ";

	out << endl;

	return 0;
}