#include <fstream>
#include <vector>

int main(){
	std::ifstream fin("bfs.in");
	std::ofstream fout("bfs.out");

	unsigned n,m,s;
	fin>>n>>m>>s;

	std::vector<int> cost(n+1,-1);

	std::vector< std::vector<int> > Adj(n+1);

	for(unsigned i=0;i<m;++i){
		unsigned a,b; fin>>a>>b;
		Adj[a].push_back(b);
	}

	std::vector<unsigned> q(n);
	q[0]=s; cost[s]=0;
	unsigned left=0,right=1;

	while(left<right){
		unsigned t=q[left++];
		for(auto it=Adj[t].begin();it!=Adj[t].end();++it){
			if(cost[*it]==-1){
				cost[*it]=cost[t]+1;
				q[right++]=*it;
			}
		}
	}

	for(unsigned i=1;i<=n;++i) fout<<cost[i]<<' ';
	fout<<'\n';
}