/*
 * Autor: Paul Herman
 * Problema: adunarea a doua numere
 * Data: 25.01.2012
 * Punctaj: 100
 * Link: http://www.infoarena.ro/problema/bfs
 */
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int s; //Sursa din care pornim cautarea
int n; //Nr de noduri
int m; //Nr de muchii
int dist[100001]; //Distanta de la sursa
vector<int> graf[100001]; //Vectori de adiacenta
int nivel; //Nivelul in arborele BFS
int elem_nivel; //Elemente ramase in nivelul curent al arborelui
queue<int> coada; //Coada pt BFS

inline void citire()
{
	int a, b;
	ifstream fin("bfs.in");
	fin >> n >> m >> s;
	for (int i = 0; i < m; i++)
	{
		fin >> a >> b;
		graf[a].push_back(b);
	}
	fin.close();
}
inline void scriere()
{
	ofstream fout("bfs.out");
	for (int i = 1; i <= n; i++)
		fout << dist[i] << ' ';
	fout.close();
}
void bfs()
{
	for (int i = 1; i <= n; i++)
		dist[i] = -1;
	int nod = s;
	coada.push(s);
	nivel = 0;
	elem_nivel = coada.size();
	while (coada.empty() == false)
	{
		nod = coada.front();
		coada.pop();
		dist[nod] = nivel;
		elem_nivel--;
		for (int i = 0; i < graf[nod].size(); i++)
			if (dist[graf[nod][i]] == -1)
				coada.push(graf[nod][i]);
		if (elem_nivel == 0)
		{
			nivel++;
			elem_nivel = coada.size();
		}
	}
}
int main()
{
	citire();
	bfs();
	scriere();
	return 0;
}