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

using namespace std;

int m, n, s;
int i, j;
vector< vector<int> > graph;
vector<int> visited;

void bfs(int vertex){

	if (vertex<0 || vertex>n - 1){
		return;
	}
	queue<int> q;
	int element;
	q.push(vertex);
	visited[vertex] = 0;
	while (!q.empty()){
		element = q.front();
		for (i = 0; i < graph[element].size(); i++)
		{
			if (visited[graph[element][i]]==-1)
			{
				q.push(graph[element][i]);
				visited[graph[element][i]] = visited[element]+1;
			}
		}
		q.pop();
	}
}

int main()
{
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	fin >> n >> m >> s;
	graph.resize(n);
	visited.resize(n, -1);
	int x, y;
	for (i = 0; i < m; i++)
	{
		fin >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
	}
	bfs(s-1);
	for (i = 0; i < n; i++)
	{
		fout << visited[i]<<" ";
	}
	fin.close();
	fout.close();
	return 0;
}