#include <iostream>
#include <queue>
#include <map>
#include <fstream>
#include <algorithm>

using namespace std;

int cost[100000];
map<int,vector<int>> LisAd;
int N, M, S, aux, i, j, index, val;


void constrListAd()
{

	ifstream f("bfs.in");
	f >> N >> M >> S;
	
	for (i = 1; i <= M; i++)
	{
		f >> index >> val;
		LisAd[index].push_back(val);
	}



}

int main() {

	queue<int> coada;
	constrListAd();
	coada.push(S);

	for (int i = 1; i <= N; i++)
		sort(LisAd[i].begin(), LisAd[i].end());

	while (!coada.empty()) {
		aux = coada.front();
		coada.pop();
		for(int nod : LisAd[aux])
			if(cost[nod] == 0 && nod != S)
			{
				cost[nod] = cost[aux] + 1;
				coada.push(nod);
			}


	}

	ofstream g("bfs.out");
	for (int i = 1; i <= N; i++)
		if (cost[i] != 0 || i == S)
			g << cost[i] << " ";
		else
		{
			cost[i] = -1;
			g << cost[i] << " ";
		}

}