#include <fstream>
#include <queue>

using namespace std;

int main(){
	
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");

	int n, m, a, b, s, count = 0;
	queue<int> q;
	vector<vector<int>> adiacenta;
	vector<int> isInQueue;
	vector<int> dist;

	fin >> n >> m >> s;

	/* initialisation  */
	vector<int> v;
	for(int i = 0; i < n; i++){
		adiacenta.push_back(v);
		isInQueue.push_back(false);
		dist.push_back(-1);
	}

	for(int i = 0; i < m; i++){
		fin >> a >> b;
		adiacenta[--a].push_back(--b);
	}

	/* perform BFS starting from "S" node */
	q.push(--s);
	isInQueue[s] = true;
	dist[s] = 0;

	while(q.size()){
		int x = q.front();
		q.pop();
		/* push every child */
		for(int i = 0; i < adiacenta[x].size(); i++){
			int elem = adiacenta[x].at(i);
			if(!isInQueue[elem]){
				isInQueue[elem] = true;
				q.push(elem);
				dist[elem] = dist[x] + 1;
			}
		}
	}

	for(int i = 0; i < n; i++){
		fout << dist[i] <<" ";
 	}
	fout<<"\n";
}