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

using namespace std;
class Graph{
	int vertices;
	vector<list<int> > adList;

public:
	Graph(int V);

	void addEdge(int x, int y);

	void BFS(int start);
};

Graph::Graph(int V){
	this->vertices = V;
	adList.resize(V + 1);
}

void Graph::addEdge(int x, int y){
	adList[x].push_back(y);
}

void Graph::BFS(int start){

	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;
				visited[*i] = 1;
			}
	}

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

int main(){

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

	Graph gr(vertices);

	for(int i = 0; i < edges; i++){
		f >> x >> y;
		gr.addEdge(x, y);
	}
	f.close();
	gr.BFS(s);

}