#include <cstdio>

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

node* v[100010];
int sel[100010];
int st[100010];
int cost[100010];

int main(){
	freopen("bfs.in","rt",stdin);
	freopen("bfs.out","wt",stdout);
	
	int m,n,s;
	
	
	scanf("%d%d%d",&n,&m,&s);
	
	int i,j;
	node* tmp;
	
	for(i=0;i<n;i++)
		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;
}