//BFS cu STL
#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
using namespace std;
int n,m,s,viz[100001],dr[100001];
vector <int> v[100001];
deque <int> coada;
void citire()
{
	ifstream fin("bfs.in");
	fin>>n>>m>>s;
	int a,b;
	for (int i=0;i<m;i++)
	{
		fin>>a>>b;
		v[a].push_back(b);
	}
	fin.close();
}	

void bfs(int in)
{
	coada.push_back(in);
	dr[in]=0;
	viz[in]=1;
	do
	{
		int x=coada.front();
		for (int i=0;i<v[x].size();i++)
			if (viz[v[x][i]]==0)
			{
				coada.push_back(v[x][i]); 
				dr[v[x][i]]=dr[x]+1;
				viz[v[x][i]]=1;
			}
		coada.pop_front();
	}while (coada.empty()==0);
}
	
int main ()
{
	citire();
	for (int i=0;i<=n;i++) dr[i]=-1; //memset(dr,-1,sizeof(dr));
	bfs(s);
	
	ofstream fout("bfs.out");
	for (int i=1;i<=n;i++) fout<<dr[i]<<' ';
	fout.close();
	return 0;
}