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

using namespace std;

int main(){

	int vertices, edges, start;
	int x, y;
	
	ifstream f("bfs.in");
	f >> vertices >> edges >> start;

	vector<int> adList[vertices + 1];

	for(int i = 0; i < edges; i++){
		f >> x >> y;
		adList[x].push_back(y);
	}
	f.close();

	queue<int> q;
	vector<int> visited(vertices + 1, 0);
	vector<int> costs(vertices + 1, -1);

	q.push(start);
	visited[start] = 1;
	costs[start] = 0;

	while(!q.empty()){

		int current = q.front();
		q.pop();

		int i, value;
		for(i = 0; i < adList[current].size(); i++){
			value = adList[current][i];
			if(visited[value] == 0){
				q.push(value);
				costs[value] = costs[current] + 1;
				visited[value] = 1;
			}
		}
	}

	ofstream g("bfs.out");
	for(int i = 1; i < vertices + 1; i++)
		g << costs[i] << " ";

	return 0;

}