#include<fstream>
#include<vector>
#include<queue>
#define dim 100007

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");
int i,j,n,m,x,nod,nd,y,t,D[dim];
vector<int>G[dim];
void bfs() {
	queue<int>q;
	for(i=1;i<=n;++i){
		D[i]=200000;
	}
	nod=t;
	D[nod]=0;
	q.push(nod);
	
	while( !q.empty() ) {
		nod=q.front();
		q.pop();
		for(int i=0;i<G[nod].size();++i) {
			nd=G[nod][i];
			if(D[nd]>D[nod]+1){
				D[nd]=D[nod]+1;
				q.push(nd);
			}
		}
	}
	for(i=1;i<=n;++i){
		if(D[i]==200000){
			g<<"-1 ";
			continue;
		}
		if(i==t){
			g<<"0 "; 
		}
		else
			g<<D[i]<<" ";
	}
}
int main (){
	
	f>>n>>m>>t;
	
	
	for(i=1;i<=m;++i) {
		
		f>>x>>y;
		G[x].push_back(y);
		
		
	}
	bfs();
	
	return 0;
}