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

#define INFILE "bfs.in"
#define OUTFILE "bfs.out"

using std::ifstream;
using std::ofstream;
using std::vector;
using std::queue;

int main()
{
	ifstream fin(INFILE);
	ofstream fout(OUTFILE);
	int m, n, s;
	vector<vector<int> > vecini;
	vector<int> vizitat;
	
	fin >> n >> m >> s;
	vecini.reserve(n);
	vizitat.reserve(n);
	for (auto i = 0; i < n; ++i) {
		vector<int> v;
		vecini.push_back(v);
		if (i == s - 1)
			vizitat.push_back(0);
		else
			vizitat.push_back(-1);
	}
	for (auto i = 0; i < m; ++i) {
		int a,b;
		fin >> a >> b;
		vecini[a-1].push_back(b-1);
	}
	fin.close();
	queue<int> q;
	q.push(s-1);
	while (!q.empty()){ 
		int x = q.front();
		q.pop();
		for (auto&i : vecini[x]){
			if (vizitat[i] == -1) {
				vizitat[i] = vizitat[x] + 1;
				q.push(i);
			}
		}
	}
	for (auto &i : vizitat)
		fout << i << " ";
	fout.close();
	return 0;
}