//VASS PETER 2013-11-21
//N M S
#include <vector>
#include <fstream>
#include <queue>
#include <map>
#include <set>
using namespace std;
int main(){
	ifstream ifs("bfs.in");
	ofstream ofs("bfs.out");
	
	int N,M,S;
	ifs>>N>>M>>S;S--;
	
	map<int,set<int> > g;
	vector<int> o(N,-1);
	
	for(int i=0;i<M;i++){
		int x,y;
		ifs>>x>>y;
		if(x!=y) g[x-1].insert(y-1);
	}
	
	queue<int> q;
	q.push(S);
	o[S]=0;
	while(!q.empty()){
		set<int>::iterator it;
		int f=q.front();
		
		for(it=g[f].begin();it!=g[f].end();it++){
			if(o[*it]==-1){	
				o[*it]=o[f]+1;
				g[*it].erase(f);
				q.push(*it);
			}
		}
		q.pop();
	}
	for(int i=0;i<N-1;i++)
		ofs<<o[i]<<" ";
	ofs<<o[N-1]<<"\n";
}