#include<fstream>
#include<queue>
#include<cstdlib>
#define NMAX 100010

using namespace std;

int n, m, s, nr[NMAX], *a[NMAX], vz[NMAX];

struct coada
{
	int x, y;
};
queue<coada> q;

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

void Citeste()
{
	int i, x, y;
	
	f>>n>>m>>s;
	
	for (i=1; i<=m; ++i)
	{
		f>>x>>y;
		nr[x]++;
		a[x]=(int *)realloc(a[x], nr[x]*sizeof(int));
		a[x][nr[x]-1]=y;
	}
}

void BFS()
{
	int i;
	coada r, w;
	
	for (i=1; i<=n; ++i) vz[i]=-1;
	vz[s]=0;
	
	r.x=s;
	for (i=0; i<nr[s]; ++i)
	{
		r.y=a[s][i]; 
		if (vz[a[s][i]]==-1) vz[a[s][i]]=1;
		q.push(r);
	}
	
	while (!q.empty())
	{
		r=q.front(); q.pop();
		for (i=0; i<nr[r.y]; ++i)
			if (vz[a[r.y][i]]==-1)
			{
				w.x=r.y;
				w.y=a[r.y][i];
				vz[w.y]=vz[w.x]+1;
				q.push(w);
			}
	}
	
	for (i=1; i<=n; ++i) g<<vz[i]<<" ";
	g<<"\n";
}

int main()
{
	Citeste();
	BFS();
	f.close();
	g.close();
	return 0;
}