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