#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

long j,x,y,z,b,c,viz[10001],k,d;
queue<int> coada;
vector<int> a[10001];
vector<int>::iterator i;

int main()
{
	fstream f,g;
	f.open("bfs.in",ios::in);
	g.open("bfs.out",ios::out);

	f>>x>>y>>z; // y=n ; x=nod ul de start
	for( j=1; j<=y; ++j)
	{	
		f>>b>>c;
		a[b].push_back(c);	
	}
	
	memset(viz,-1,sizeof(viz));
	viz[x]=0;
	coada.push(x);
	while(!coada.empty())
	{
		d=coada.front();
		coada.pop();
		for(i=a[d].begin();i!=a[d].end();++i)
			if(viz[*i] == -1)
			{	viz[*i] = viz[d]+1;
				coada.push(*i);
			}
	}
	for(k=1 ; k<=x; k++)
		g<<viz[k]<<" ";

	return 0;
}