#include<fstream.h>
ifstream intrare("bfs.in");
ofstream iesire("bfs.out");
#define maxn 100002
#define maxm 1000002
int n,m,s;
int vizitat[maxn];
int lista[maxm][2];
int start[maxn];
int coada[maxn];
void citeste()
{
	intrare>>n>>m>>s;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		intrare>>a>>b;
		lista[i][0]=b;
		lista[i][1]=start[a];
		start[a]=i;
		
	}
	vizitat[s]=1;
	coada[1]=s;
}
void parcurge()
{
	int max=1,min=1;
	int nod;
	//coada[1]=1;
	while(max>=min)
	{
		nod=coada[min];
		int st=start[nod];
		while(st!=0)
		{
			int ver=lista[st][0];
			if(vizitat[ver]==0)
			{
				vizitat[ver]=vizitat[nod]+1;
				coada[++max]=ver;
			}
			st=lista[st][1];
		}
		min++;
	}
}
void afiseaza()
{
	for(int i=1;i<=n;i++)
	{
		if(vizitat[i]==0)iesire<<"-1 ";
		else iesire<<vizitat[i]-1<<" ";
	}
}
int main()
{
	citeste();
	parcurge();
	afiseaza();
	return 0;
}