#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
#define MaxN 100005
#define MaxM 1000005

ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector<int> G[MaxN];
int Drum[MaxN],viz[MaxN];
int N,M,S;

void citire(){
	fin>>N>>M>>S;
	
	int x,y;
	for(int i=1;i<=M;i++){
		fin>>x>>y;
		G[x].push_back(y);
	}
}

void bfs(){
	int Stiva[MaxM];
	int prim=0,ultim=0,x;
	Stiva[ultim++]=S;
	Drum[S]=0,viz[S]=1;
	while(prim<=ultim){
		x=Stiva[prim];
		for(int i=0;i<G[x].size();i++){
			if(!viz[G[x][i]]){
				viz[G[x][i]]=1;
				Stiva[ultim++]=G[x][i];
				Drum[G[x][i]]=Drum[x]+1;
			}
		}
		prim++;
	}
}

int main(){
	
	citire();
	
/*	for(int i=1;i<=N;i++){
		for(int j=0;j<G[i].size();j++){
			cerr<<G[i][j]<<" ";
		}
		cerr<<"\n";
	}*/
	
	for(int i=1;i<=N;i++) Drum[i]=-1;
	
	bfs();
	
	for(int i=1;i<N;i++)
		fout<<Drum[i]<<" ";
	fout<<Drum[N]<<"\n";
	
	fout.close();
	fin.close();
	return 0;
}