//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#define FOR(i,x,n) \
	for(int i = x;i <= n;i++)
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n, m, s, noduri[100001];
vector <int> v[100001];
void read() {
	f >> n >> m >> s;
	FOR(i, 1, m) {
		int x, y;
		f >> x >> y;
		v[x].push_back(y);
		}
	FOR(i, 1, n)noduri[i] = -1;
}

void solve() {
	queue<int> que;
	que.push(s);
	noduri[s] = 0;
	while (!que.empty()) {
		int r = que.front();
		FOR(i, 0, v[r].size()-1) 
			if (noduri[v[r][i]] == -1) {
				que.push(v[r][i]);
				noduri[v[r][i]] = noduri[r] + 1;
			}
				que.pop();

		}
		FOR(i, 1, n)g << noduri[i] << ' ';

	}


int main()
{
	read();
	solve();
	/*FOR(i, 1, n) {
		cout << i << " = ";
		FOR(j, 0, v[i].size() - 1)cout << v[i][j];
		cout << endl;
	}*/
	//cout << endl;
	//system("pause");
    return 0;
}