/*
 * 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 <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

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()
{
	int nod = s;
	int nivel = 0;
	vector<int> coada;
	int nc = 0;
	int elem_nivel = 1;
	for (int i = 1; i <= n; i++)
		dist[i] = -1;
	coada.push_back(s);
	while (nc < coada.size())
	{
		if (elem_nivel == nc)
		{
			nivel++;
			elem_nivel = coada.size() + 1;
		}
		nod = coada[nc];
		dist[nod] = nivel;
		for (int i = 0; i < graf[nod].size(); i++)
			if (dist[graf[nod][i]] == -1)
				coada.push_back(graf[nod][i]);
		nc++;
	}
}
int main()
{
	citire();
	bfs();
	scriere();
	return 0;
}