#include<fstream.h>
#define NM 100000

ifstream in("bfs.in");
ofstream out("bfs.out");
int c[NM],viz[NM],d[NM],n,m,start,li=1,ls;

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

nod *v[NM];

void add(nod *&l,int x){
nod *n=new(nod);
n->x=x;
n->next=l;
l=n;

}

int c_vida(){return ls<li;}
void pune(int x){c[++ls]=x;}
void scoate(int &x){x=c[li++];}

void build(){
int i,a,b;
in>>n>>m>>start;
for(i=1;i<=m;i++)
	{
	in>>a>>b;
	add(v[a],b);
	}
}

void bf(int start)
{
	int a,b;
	nod *nc;
	pune(start);
	viz[start]=1;
	while(!c_vida())
		{
			scoate(a);
			nc=v[a];
			while(nc)
				{
					b=nc->x;
					if(!viz[b])
						{
							pune(b);
							viz[b]=1;
							d[b]=d[a]+1;
						}
					nc=nc->next;
				}
			}
}

int main(){
int i;
build();
bf(start);
for(i=1;i<=n;i++)
	if(d[i]==0&&i!=start)
		d[i]=1;
for(i=1;i<=n;i++)
	out<<d[i]<<" ";
return 0;
}