#include<fstream>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
struct nod{ int c;
			nod*lg;
		  }*vf[1000000],*r;
int p,q,n,m,i,s,x,y,que[5000000],ave[1000000];
int main()
{
  f>>n>>m>>s;
  for(i=1;i<=n;i++) { vf[i]=new nod;
	                  vf[i]->c=0;
					  vf[i]->lg=0;
					}  
  for(i=1;i<=m;i++) { f>>x>>y; 
 					  r=new nod;r->c=y;
					  r->lg=vf[x]->lg;
					  vf[x]->c++;
					  vf[x]->lg=r;
					}
  p=q=1;
  ave[s]=1;que[1]=s;
  while(p<=q) { r=vf[que[p]]->lg;
			    while(r) { if(!ave[r->c]) { que[++q]=r->c;
											ave[r->c]=1+ave[que[p]];
										  }
						   r=r->lg;
						 }
			    p++;
              }		
  for(i=1;i<=n;i++)g<<ave[i]-1<<' ';g<<'\n'; 
  f.close();
  g.close();
  return 0;
}