#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

int a,b,n,k,m,i,s,nod[100005],p;
vector<int> veci[100005];
deque<int> co;

int main() {

	fin>>n>>m>>s;
	for(i=1;i<=n;i++)
		nod[i]=-1;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		veci[a].push_back(b);
	}
	
	co.push_back(s);
	nod[s]=0;
	while(!co.empty())
	{
		p=co.front();
		co.pop_front();
		for(i=0;i<veci[p].size();i++)
		{
			if(nod[veci[p][i]]==-1)
			{
				nod[veci[p][i]]=nod[p]+1;
				co.push_back(veci[p][i]);
			}
		}
	}
	for(i=1;i<=n;i++)
		fout<<nod[i]<<" ";
}