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

#define nmax 100001
using namespace std;

vector<int> L[nmax];
int D[nmax];
queue<int> Q;

int main(){
	ifstream f("bfs.in", ios::in);
	ofstream g("bfs.out", ios::out);

	int N, M, S;

	f >> N >> M >> S;

	for (int i = 1; i <= N; ++i){
		D[i] = -1;
	}
	D[S] = 0;

	int x, y;
	for (int i = 0; i < M; i++){
		f >> x >> y;
		L[x].push_back(y);
	}

	//BFS
	Q.push(S);
	while (!Q.empty()){
		x = Q.front();
		Q.pop();
		for (int i = 0; i < L[x].size(); i++){
			if (D[L[x][i]] == -1){
				Q.push(L[x][i]);
				D[L[x][i]] = D[x]+1;
			}
		}
	}

	for (int i = 1; i <= N; i++)
		g << D[i] << " ";
	g << endl;

	f.close();
	g.close();
	return 0;
}