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

struct nod
{
	int nivel;
	int v;
};

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<nod> 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;
	nod nt, nc;
	nt.nivel = 0;
	nt.v = s;
	coada.push(nt);
	while (coada.empty() == false)
	{
		nc = coada.front();
		nt.nivel = nc.nivel + 1;
		coada.pop();
		dist[nc.v] = nc.nivel;
		for (int i = 0; i < graf[nc.v].size(); i++)
		{
			if (dist[graf[nc.v][i]] == -1)
			{
				nt.v = graf[nc.v][i];
				coada.push(nt);
			}
		}
	}
}
int main()
{
	citire();
	bfs();
	scriere();
	return 0;
}