#include <cstdio>

struct node{
	node* next;
	int id;
};

int main(){
	freopen("bfs.in","rt",stdin);
	freopen("bfs.out","wt",stdout);
	
	int m,n,s;
	node* v[100002];
	int sel[100002];
	int st[100002];
	int cost[100002];
	
	scanf("%d%d%d",&n,&m,&s);
	
	int i,j;
	node* tmp;
	
	for(i=0;i<n;i++){
		v[i]=NULL;
		sel[i]=0;
		cost[i]=-1;
	}
	
	for(i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		
		tmp=new node;
		tmp->id=b;
		tmp->next=v[a];
		v[a]=tmp;
	}
	
	int stl=1,l=0;
	st[0]=s;
	cost[s]=0;
	sel[s]=1;
	
	while(l<stl){
		for(tmp=v[st[l]];tmp;tmp=tmp->next)
			if(!sel[tmp->id]){
				cost[tmp->id]=cost[st[l]]+1;
				st[stl++]=tmp->id;
				sel[tmp->id]=1;
			}
		l++;
	}
	for(i=1;i<=n;i++)
		printf("%d ",cost[i]);
	
	return 0;
}