#include <iostream>
#include <string.h>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 100000

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

int N, M, S;
vector <int> G[NMAX];
int shortest_path[NMAX];

void read(void)
{
	int x, y;
	fin >> N >> M >> S;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y;
		G[x].push_back(y);
	}
}

void bfs(void)
{
	memset(shortest_path, -1, sizeof(int) * (N + 1) );
	shortest_path[S] = 0;
	queue <int> path;
	path.push(S);
	int node;
	while (!path.empty())
	{
		node = path.front();
		path.pop();
		for (unsigned int i = 0; i < G[node].size(); i++)
		{
			int curr_node = G[node].at(i);
			if (shortest_path[curr_node] == -1)
			{
				shortest_path[curr_node] = shortest_path[node] + 1;
				path.push(curr_node);
			}
		}
	}
}

void print(void)
{
	for (int i = 1; i <= N; i++)
	{
		fout << shortest_path[i] << ' ';
	}
}

int main(void)
{
	read();
	bfs();
	print();
}