#include <fstream>
using namespace std;

long a[1000][1000],cost[100001],viz[100001],p,u,n,m,start,c[100001];

void citire(){
	ifstream f("bfs.in");
	f>>n>>m>>start;
	long i,x,y;
	for(i=1;i<=m;i++){
		f>>x>>y;
		a[x][0]++;
		a[x][a[x][0]]=y;}
	f.close();}

void bfs(){
	int nod,i;
	do{
		nod=c[p];
		p++;
		for(i=1;i<=a[nod][a[nod][0]];i++)
			if(viz[a[nod][i]]==0){
				u++;
				c[u]=a[nod][i];
				viz[c[u]]=1;
				cost[c[u]]=cost[nod]+1;}}
	while(p<=u);}

void afisare(){
	ofstream g("bfs.out");
	for(int i=1;i<=n;i++)
		g<<cost[i]<<" ";
	g.close();}

int main(){
	citire();
	int i;
	for(i=1;i<=n;i++)
		cost[i]=-1;
	cost[start]=0;
	viz[start]=1;
	c[1]=start;
	p=u=1;
	bfs();
	afisare();
	return 0;}