#include<fstream>
#include<queue>
#include<iterator>
using namespace std;

struct csucs {
	vector<int>szomszedok;
	int tavolsag = -1;
};

int main() {
	ifstream in("bfs.in");
	int N, M, S;
	in >> N >> M >> S;
	csucs* csucsok = new csucs[N];
	for (int i = 0;i < M;++i) {
		int honnan, hova;
		in >> honnan >> hova;
		csucsok[honnan-1].szomszedok.push_back(hova-1);
	}

	csucsok[S - 1].tavolsag = 0;
	queue<int> q;
	q.push(S-1);
	while(true)
	{
		S = q.back();
		q.pop();
		for (vector<int>::iterator it = csucsok[S].szomszedok.begin();
			it != csucsok[S].szomszedok.end();++it)
			if (csucsok[*it].tavolsag==-1) {
				q.push(*it);
				csucsok[*it].tavolsag = csucsok[S].tavolsag + 1;
			}
		if (q.empty()) break;
	}

	ofstream out("bfs.out");
	for (int i = 0;i < N;++i) {
		out << csucsok[i].tavolsag << " ";
	}
}