#include<fstream>

using namespace std;

ifstream cin("bfs.in");
ofstream cout("bfs.out");

int n, m, st, c[100005], prim, ultim, drum[100005],  k=0, init;
bool viz[100005];

struct nod{
	int val;
	nod *next;
};

nod *L[100005], *p;

void bfs(){
	while(prim<=ultim){
		p=L[c[prim]];
		while(p){
			if(viz[p->val]==0){
				viz[p->val]=1;
			++ultim; drum[p->val]=drum[c[prim]]+1;
			c[ultim]=p->val;
			}
			p=p->next;
		}
		++prim;
	}
}

void afisare(int r){
	nod *w=L[r];
	while(w){
		cout<<w->val<<"  ";
		w=w->next;
	}
	cout<<"\n";
}

int main(){
	cin>>n>>m>>st;
	
	while(m--){
		int x, y;
		cin>>x>>y;
		p=new nod;
		p->val=y;
		p->next=L[x];
		L[x]=p;
	}
	
	prim=ultim=1; viz[st]=1;
	c[prim]=st; drum[st]=0;
	bfs(); init=st;
	
/*	for(int i=1; i<=n; ++i){
		 cout<<c[i]<<"  ";
	}
*/
	for(int i=1; i<=n; ++i){
	if(drum[i]==0 && i!= init) drum[i]=-1;
	cout<<drum[i]<<"  ";
}
/*
for(int i=1; i<=n; ++i){
	afisare(i);
}*/

	

	
	return 0;
}