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

using namespace std;

int n,m,s,d[MAX],aa[MAX];
bool done[MAX];

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


int main(){
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	
	int i,temp1,temp2,k;
	
	
	
	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_back(temp2);
		aa[temp1]++;
	}
	
	while(!qe.empty()){
		temp1=qe.front();temp2=qd.front();
		
		if(!done[temp1]){
			
		d[temp1]=temp2;
		done[temp1]=true;
		
		for(i=0;i<aa[temp1];i++){
			k=a[temp1][i];
			qe.push(k);
			qd.push(temp2+1);
		}
		}
		
		qe.pop();
		qd.pop();
	}
	
	for(i=1;i<=n;i++){
	
		printf("%d ",d[i]);
	}
	
	return 0;}