#include <fstream>
using namespace std;

struct arc{int x,y;} a[1<<20];
int s[1<<17],v[1<<17],c[1<<17],n,m,t;

ifstream in("bfs.in");
ofstream out("bfs.out");

bool cmp(arc a,arc b)
{
	return a.x<b.x;
}

void set(int x)
{
	int i,p=0,u=0;
	v[x]=0;
	c[++u]=x;
	while (p<u)
		for (x=c[++p],i=s[x];i<s[x+1];i++)
			if (v[a[i].y]==-1)
			{
				v[a[i].y]=v[x]+1;
				c[++u]=a[i].y;
			}
}
	
int main()
{
	int i,j;
	in>>n>>m>>t;
	for (i=1;i<=m;i++)
		in>>a[i].x>>a[i].y;
	sort(a+1,a+m+1,cmp);
	for (i=j=1;i<=n;i++)
	{
		for (;j<=m && a[j].x<i;j++);
		s[i]=j;
		v[i]=-1;
	}
	s[n+1]=m+1;
	set(t);
	for (i=1;i<=n;i++)
		out<<v[i]<<" ";
	out<<"\n";
	return 0;
}