#include <fstream>
#include <map>
#include <queue>
#include <tr1/unordered_map>

using namespace std;
using namespace tr1;

ifstream in("bfs.in");
ofstream out("bfs.out");

unordered_map <int,vector<int> > graph;
unordered_map <int,bool> visited;
unordered_map <int,int> result;
int n,m,s;

void read(){
	in>>n>>m>>s;
	int i,x,y;
	for(i=1;i<=m;++i){
		in>>x>>y;
		graph[x].push_back(y); // exista arc de la x la y
	}
}

void bf(){
	int currentnode;
	int currentdistance;
	queue <int> coada;
	vector <int> neighbours;
	vector <int>::iterator it;
	coada.push(s);
	int i;
	for(i=1;i<=n;++i){
		visited[i]=false;
		result[i]=-1;
	}
	result[s]=0;
	visited[s]=true;
	while(!coada.empty()){
		currentnode=coada.front();
		currentdistance=result[currentnode];
		coada.pop();
		neighbours=graph[currentnode];
		for(it=neighbours.begin();it!=neighbours.end();++it){
			if(visited[*it]==true)
				continue;
			coada.push(*it);
			result[*it]=currentdistance+1;
			visited[*it]=true;
		}
	}
	for(i=1;i<=n;++i){
		out<<result[i]<<" ";
	}
}

int main(){
	read();
	bf();
}