#include<fstream>
#include<vector>
using namespace std;
#define MAXN 1<<20
int n,m,x;
vector <int> v[MAXN];
int cost[MAXN],s[MAXN],g[MAXN];
void citire ()
{
	ifstream fin("bfs.in");
	fin>>n>>m>>x;
	int i,a,b;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		v[a].push_back(b);
		
	}
	for(i=1;i<=n;i++)
		g[i]=v[i].size();
	fin.close();
}
void bfs(int nod)
{
	int i,l=1,j;
	memset(cost,-1,sizeof(cost));
	cost[nod]=0;
	s[l]=nod;
	for(i=1;i<=l;i++)
		for(j=0;j<g[s[i]];j++)
		{
			if(cost[v[s[i]][j]]==-1)
			{
				s[++l]=v[s[i]][j];
				cost[s[l]]=cost[s[i]]+1;
			}
		}
}
int main ()
{
	citire();
	bfs(x);
	int i;
	ofstream fout("bfs.out");
	for(i=1;i<=n;i++)
		fout<<cost[i]<<' ';
	fout.close();
	return 0;
}