#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#ifndef inf
#define inf 9999999
#endif

std::ifstream f("bfs.in");
std::ofstream g("bfs.out");
 
std::queue<int> coada;
std::vector<bool> viz;
std::vector<int> dim;

int vf, muc, start;
int adiac[10000][1000];

void citire();
void initalizare();
void bfs();
void afisare();

int main(){
	
	citire();
	initalizare();
	bfs();
	afisare();
	return 0;
}

void citire(){
	/*
		Functia citeste un graf din fisier si il reprezinta prin liste
			de adiacenta
	 */

	int x, y;
	f >> vf >> muc >> start;
	for(int i = 0 ; i < muc; i++){
		f >> x >> y;
		adiac[x][0]++;
		//adiac[y][0]++;
		adiac[x][adiac[x][0]] = y;
		//adiac[y][adiac[y][0]] = x;
	}
}

void initalizare(){
	viz.resize(vf+1);
	dim.resize(vf+1);
	for(int i = 1; i <= vf; i++)
		dim[i] = inf;

	for(int i = 1; i <= vf; i++)
		viz[i] = false;	
}


void bfs(){

	int curent = 0;
	coada.push(start);
	dim[start] = 0;
	viz[start] = true;
	while(!coada.empty()){
		curent = coada.front();
		coada.pop();
		for(int i = 1; i <= adiac[curent][0]; i++){
			if(viz[adiac[curent][i]] == false){
				viz[adiac[curent][i]] = true;
				dim[adiac[curent][i]] = dim[curent] + 1;
				coada.push(adiac[curent][i]);
			}
		}
	}
}


void afisare(){

	
	for(int i = 1; i <= vf; i++){
		if(dim[i] == inf)
			g << "-1 ";
		else
			g << dim[i] << " ";
	} 
	
}