#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
#define dim 100003
vector <int> v[dim];
bitset <dim> vizitat;
int cost[dim];
queue <int> coada;

void bfs(int x)
{
	coada.push(x);
	int inc=1,sf=1;
	while(!coada.empty())
	{
		x=coada.front();
		
		for(int k=0;k<v[x].size();++k)
		{
			if(!vizitat[v[x][k]])
			{
				vizitat[v[x][k]]=1;
				coada.push(v[x][k]);
				if(cost[v[x][k]]==-1)
					cost[v[x][k]]=cost[x]+1;
			}
		}
		coada.pop();
	}
}
				


int main()
{
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int i, a, b, n, m, s;
	
	fin>>n >>m >>s;
	
	for(i=1;i<=m;++i)
	{
		fin>>a >>b;
		v[a].push_back(b);
	}
	
	for(i=1;i<=n;++i)
		cost[i]=-1;
	cost[s]=0;
	
	bfs(s);
	
	for(i=1;i<=n;++i)
		fout<<cost[i] <<" ";
	
	return 0;
}