#include<fstream>
#include<iostream>
using namespace std;
unsigned long n,m,s,a[20001][20001],v[20001],viz[20001];
int rec(unsigned long x,unsigned long nr)
{
	unsigned long i,v2[20001],q=0;
	for(i=1;i<=n;i++)
		if(a[x][i] && !viz[i])
		{
			viz[i]=1;
			v[i]=nr;
			q++;
			v2[q]=i;
			
		}
	for(i=1;i<=q;i++)
		rec(v2[i],nr+1);
}
			
int main()
{
	unsigned long i,xx,yy,q;
	ifstream f("bfs.in");
	f>>n>>m>>s;
	
	for(i=1;i<=m;i++)
	{
		f>>xx>>yy;
		a[xx][yy]=1;
	}
	
	rec(s,1);
	ofstream g("bfs.out");
	for(i=1;i<=n;i++)
		if(i==s) g<<"0 ";
		else if(v[i]==0) g<<"-1 ";
		else g<<v[i]<<" ";
}