/*
 	Parcurgerea in latime. Implementare cu liste de adiacenta implementate prin vectori alocati dinamic.
 */

#include <fstream>
#include <iostream>
#include <cstdlib>
#define MAX 100001
using namespace std;
int *a[MAX], v[MAX], coada[MAX], dist[MAX], s, n;

void read();
void bfs();
void write();

void read(){
	int m;
	ifstream fin("bfs.in");
	fin>>n>>m>>s;
	for(int i = 1;i<=n;i++){
		a[i] = (int *) malloc(sizeof(int) * 1);
		a[i][0] = 0;
	}
	for( ; m ; m--){
		int i,j;
		fin>>i>>j;
		a[i] = (int *) realloc(a[i], sizeof(int) * (a[i][0]+2));
		a[i][++a[i][0]] = j;
	}
	fin.close();
}

void write(){
	ofstream fout("bfs.out");
	for (int i = 1 ; i <= n ; i++)
		fout<<dist[i] <<" ";
	fout.close();
}

void bfs(){
	int st=1, dr = 1;
	for(int  i =1 ; i <= n;i++)
		dist[i] = -1;
	coada[1]=s;	v[s]=1; dist[s] = 0;
	while( st <= dr ){
		int k  = coada[st++];
		for(int i = 1 ; i<=a[k][0] ; i++)
			if(v[a[k][i]] == 0){
				coada[++dr] = a[k][i];
				v[a[k][i]] = 1;
				dist[a[k][i]] = dist[k] +1;
			}
	}
}

int main(){
	read();
	bfs();
	write();
	return 0;
}