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

#define NMAX 100001

using namespace std;

ifstream fi("bfs.in");
ofstream fo("bfs.out");
int n, m, s, l, c, i, nc, vec, d[NMAX];
vector<int> v[NMAX];
queue<int> q;

int main() {
	fi >> n >> m >> s;
	for (i = 1; i <= m; i++) {
		fi >> l >> c;
		v[l].push_back(c);
	}
	for (i = 1; i <= n; i++)
    d[i] = -1;
  q.push(s); d[s] = 0;
	while (not q.empty()) {      // cat timp exista elemente in coada
		nc = q.front();      // Extragem nodul curent.
		for (i = 0; i < v[nc].size(); i++) {
      vec = v[nc][i];  // Vecinul luat din vector.
			if (d[vec] == -1) { // Este nevizitat?
			  q.push(vec);         // Punem vec in coada.
        d[vec] = d[nc]+1;
			}
		}
		q.pop(); // Scoatem din coada nodul curent.
	}
	for (i = 1; i <= n; i++)
    fo << d[i] << ' ';
	return 0;
}