#include<fstream>
#include<vector>
using namespace std;
const int MAXN=100010;
vector<int> v[MAXN];
int dist[MAXN];
int q[MAXN];
int inc=0,sf=-1;
int n,m,s;
void push(int arg)
{
	++sf;
	q[sf]=arg;
}
void pop()
{
	q[inc]=0;
	++inc;
}
void citire()
{
	int i,x,y;
	ifstream fin("bfs.in");
	fin>>n>>m>>s;
	for (i=1;i<=m;++i)
	{
		fin>>x>>y;
		v[x].push_back(y);
	}
	fin.close();
}
void bfs(int start)
{
	int aux;
	for (int i=1;i<=n;++i)
		dist[i]=-1;
	dist[start]=0;
	push(start);
	while (inc<=sf)
	{
		aux=q[inc];
		for (vector<int>::iterator i=v[aux].begin();i!=v[aux].end();++i)
		{
			if (dist[*i]==-1)
			{
				dist[*i]=dist[aux]+1;
				push(*i);
			}
		}
		pop();
	}
}
void afisare()
{
	ofstream fout("bfs.out");
	for (int i=1;i<=n;++i)
		fout<<dist[i]<<' ';
	fout<<'\n';
	fout.close();
}
int main()
{
	citire();
	bfs(s);
	afisare();
	return 0;
}