#include<fstream>
#include<iostream>
using namespace std;
int n,m,a[1000][1000],c[1000],cd[1000],s,viz[1000],l=2,prec=1;
void bfs(int nod)
{

	for(int i=1; i<=n; i++)
		{
			
			if(a[nod][i]==1 && viz[i]!=1) 
			{
				cd[l++]=i; 
				c[i]=c[nod]+1;
				viz[i]=1;
			}
	}
	prec++;
	if(cd[prec]!=0)
		bfs(cd[prec]);
	
	
}
int main()
{
	ifstream f("bfs.in");
	f>>n>>m>>s;
	int i,x,y;
	for(i=1;i<=n;i++)
		c[i]=-1;
	for(i=1;i<=m;i++)
		{
			f>>x>>y;
			a[x][y]=1;
		}
	f.close();
	c[s]=0;
	cd[1]=s;
	viz[s]=1;
	bfs(s);
	ofstream g("bsf.out");
	for(i=1; i<=n; i++)
		g<<c[i]<<" ";
	g.close();
	
}