#include <fstream.h>
#define MaxN 100009
#define MaxM 1000009

int s[MaxN],T[2][2*MaxM],c[MaxN],a[MaxN],S,n,m;

void add(int x,int y,int &st)
{
	T[0][st]=y;
	T[1][st]=s[x];
	s[x]=st;
	st++;
}

void cit()
{
	int i,x,y,st=1;
	ifstream fin("bfs.in");
	fin>>n>>m>>S;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		add(x,y,st);
	}
	fin.close();
}

void BFS(int nod)
{
	int i,st=1,p;
	
	for(i=1;i<=n;i++)
		c[i]=-1;
	
	c[nod]=0;
	a[st]=nod;
	
	for(i=1;i<=st;i++)
	{
		//parcurg vecinii nodului a[i]
		p=s[a[i]];
		while(p)
		{
			if(c[T[0][p]]==-1)
			{
				st++;
				a[st]=T[0][p];
				c[T[0][p]]=c[a[i]]+1;
			}
			p=T[1][p];
		}
	}
}

void afis()
{
	int i;
	ofstream fout("bfs.out");
	for(i=1;i<=n;i++)
		fout<<c[i]<<" ";
	fout.close();
}

int main()
{
	cit();
	BFS(S);
	afis();
	return 0;
}