#include <stdio.h>
#include <queue>
#define MAX 100001

using namespace std;

int n,m,s,d[MAX];

queue<int> a[MAX],qe,qd;


int main(){
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	int i,temp1,temp2;
	
	
	
	scanf("%d %d %d",&n,&m,&s);
	
	for(i=1;i<=n;i++){d[i]=-1;}
	
	qe.push(s);
	qd.push(0);
	d[s]=0;
	
	for(i=1;i<=m;i++){
		
		scanf("%d %d",&temp1,&temp2);
		
		a[temp1].push(temp2);
	}
	
	while(!qe.empty()){
		temp1=qe.front();temp2=qd.front();
		
		if(d[temp1]==-1){d[temp1]=temp2;}
		
		while(!a[temp1].empty()){
			qe.push(a[temp1].front());
			qd.push(temp2+1);
			a[temp1].pop();
		}
		
		qe.pop();
		qd.pop();
	}
	
	for(i=1;i<=n;i++){
	
		printf("%d ",d[i]);
	}
	
	return 0;}