#include<fstream.h>
#include<iostream.h>
int a[4001][4001],sel[4001],c[4001];
int main()
{
int n,m,s,li,ls,i,k,j=0;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
fin>>n>>m>>s;
for(i=1;i<=m;i++){
				 fin>>li>>ls;
				 a[li][ls]=1;
				 }
c[1]=s;
for(i=1;i<=n;i++)sel[i]=-1;
sel[s]=0;
li=1;
ls=1;
while(li<=ls){
			 k=0;
			 for(i=1;i<=n;i++)if(a[c[li]][i] && sel[i]==-1)
											 {
											 if(!k)j++;
											 k=1;
											 sel[i]=j;
											 c[++ls]=i;
											 }
			 li++;
			 }
for(i=1;i<=n;i++)fout<<sel[i]<<' ';
return 0;
}