#include<fstream>
#include<vector>
using namespace std;
const int inf=1<<29;
const int nmax=100005;
vector<int> v[nmax];
int g[nmax],d[nmax],viz[nmax],s[nmax];
int n,m,p;
void citire ()
{
	ifstream fin("bfs.in");
	fin>>n>>m>>p;
	int x,y,i;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		v[x].push_back(y);
	}
	for(i=1;i<=n;i++)
		g[i]=v[i].size();
	fin.close();
}
void bfs(int nod)
{
	int i,j,k=1;
	memset(d,-1,sizeof(d));
	s[k]=nod;
	d[nod]=0;
	for(i=1;i<=k;i++)
		for(j=0;j<g[s[i]];j++)
			if(d[v[s[i]][j]]==-1) 
			{ 
				s[++k]=v[s[i]][j];
				d[s[k]]=d[s[i]]+1;
			}
}
int main ()
{
	citire();
	bfs(p);
	int i;
	ofstream fout("bfs.out");
	for(i=1;i<=n;i++)
		fout<<d[i]<<' ';
	fout.close();
	return 0;
}