# include <fstream>
# include <list>
# include <queue>
# include <vector>
using namespace std;
ifstream f ("bfs.in");
ofstream g ("bfs.out");

int i,n,m,s,x,y;
int main ()
{
	f>>n>>m>>s;
	
	list<int> a[n+1];
	vector<int> d(n+1,-1);
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		a[x].push_front(y);
	}
	
	queue<int> coada;
	
	coada.push(s);
	d[s]=0;
	list<int>::iterator it;
	for (i=1;i<=n;i++)
	{
		for (it=a[i].end();it!=a[i].begin();it--);
	}
	
	while (!coada.empty())
	{
		x=coada.front();
		coada.pop();
		for (it=a[x].begin();it!=a[x].end();it++)
		{
			if (d[*it]==-1)
			{
				coada.push(*it);
				d[*it]=d[x]+1;
			}
		}
	}
	
	for (i=1;i<=n;i++)
		g<<d[i]<<" ";
	
	
	
	return 0;
}