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

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

void BFS(csucs csucsok[], int jelenlegi, queue<int> q) {
	for (vector<int>::iterator it = csucsok[jelenlegi].szomszedok.begin();
		it != csucsok[jelenlegi].szomszedok.end();++it) 
		if (!csucsok[*it].visited) {
			q.push(*it);
			csucsok[*it].visited = true; 
			csucsok[*it].tavolsag=csucsok[jelenlegi].tavolsag+1;
		}
	if (q.empty()) return;
	int kovetkezo = q.back();
	q.pop();
	BFS(csucsok, kovetkezo, q);
}

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;
	csucsok[S - 1].visited = true;
	queue<int> q;
	BFS(csucsok,S-1,q);

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