#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define file_in "bfs.in"
#define file_out "bfs.out"

#define nmax 101000

int N,M;
int S,Cost[nmax];
vector<int> G[nmax];

void bfs(){
	
	int p,u,i;
	int viz[nmax];
	p=u=1;
	memset(viz,0,sizeof(viz));
	viz[S]=1;
	vector<int> :: iterator it;
	int Q[nmax];
	Q[p]=S;
	
	while(p<=u){
		int nod=Q[p];
		for (it=G[nod].begin();it!=G[nod].end();++it)
			 if (!viz[*it]){
				 viz[*it]=1;
				 Q[++u]=(*it);
				 Cost[(*it)]=Cost[nod]+1;
			 }
		p++;
	}
}	

int main(){
	
	int i,a,b;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &N, &M, &S);
	while(M--){
		
		scanf("%d %d", &a, &b);
		
		G[a].push_back(b);
    }
	 
	memset(Cost,-1,sizeof(Cost));
	Cost[S]=0;
	bfs();
	
	for (i=1;i<=N;++i)
		 printf("%d ", Cost[i]);
	
	return 0;
	
}