#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<list<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(this->vertices + 1, 0);
	vector<int> costs(this->vertices + 1, -1);

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

	while(!q.empty()){

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

		list<int>::iterator i;
		for(i = this->adList[current].begin(); i != this->adList[current].end(); i++)
			if(visited[*i] == 0){
				q.push(*i);
				costs[*i] = costs[current] + 1;
			}
	}

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

	return 0;

}