#include<fstream.h>
#include<iostream.h>
int n,m,s,coada[4001],sel[4001],li,ls,a[4001][4001];

int main()
{
int n,m,s,li,ls,i;
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;
				 }
for(i=1;i<=n;i++)sel[i]=-1;
sel[s]=0;
li=1;
ls=1;
coada[li]=s;
while(li<=ls){
			 for(i=1;i<=n;i++)if(sel[i]==-1 && a[coada[li]][i]){
															   ls++;
															   coada[ls]=i;
															   sel[i]=sel[coada[li]]+1;
															   }
			 li++;
			 }
for(i=1;i<=n;i++)fout<<sel[i]<<' ';
return 0;
}