#include <fstream>
#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>

enum Color{
	WHITE ,
	GRAY , 
	BLACK
};

enum EDGE_DIRECTION{
	BIDIRECTIONAL ,
	UNIDIRECTIONAL
};

class Node{
private:
	std::vector<int> neigh ;

public:
	void add_neighbour(int i);
	bool is_neighbour(int i);
	void remove_neighbour(int i);
	std::vector<int> & get_neigh();
	void sort();
	
	

};
void Node::sort(){
	std::sort(neigh.begin(),neigh.end());
}

void Node::add_neighbour(int i){
	if(is_neighbour(i)){
		return ; 
	}
	neigh.push_back(i);
	

}
bool Node::is_neighbour(int i){
	if (neigh.empty())
           return false;
      if (std::find(neigh.begin(), neigh.end(), i) != neigh.end())
           return true;
      else
           return false;
}
void Node::remove_neighbour(int i){
	if(!is_neighbour(i)){
		return ; 
	}
	neigh.erase(std::find(neigh.begin(), neigh.end(), i)); // stergem elementul respectiv

}
std::vector<int> & Node::get_neigh(){
	return neigh ;
}




class NodeInfo{
private:
	Color color;
	unsigned int tDesc;
	unsigned int tFin;
	unsigned int nNodeIndex;
	unsigned int dist;
	unsigned int parent ;
public:
	NodeInfo();

	//them getters
	unsigned int get_tDesc() const;
	unsigned int get_tFin() const ;
	Color get_color() const ;
	unsigned int get_nNodeIndex() const;
	unsigned int get_dist() const ;
	unsigned int get_parent()const;

	//them setters
	void set_tDesc (unsigned int tDesc);
	void set_tFin (unsigned int tFin);
	void set_nNodeIndex (unsigned int nNodeIndex);
	void set_dist (unsigned int dist);
	void set_color(Color color);
	void set_parent(unsigned int parent);

};

void NodeInfo::set_parent(unsigned int parent){
	this->parent = parent;
}
unsigned int NodeInfo::get_parent() const{
	return parent;
}
unsigned int NodeInfo::get_tDesc() const{
	return tDesc;
}
unsigned int NodeInfo::get_tFin() const {
	return tFin;
}
Color NodeInfo::get_color() const {
	return color;
}
unsigned int NodeInfo::get_nNodeIndex() const{
	return nNodeIndex;
}
unsigned int NodeInfo::get_dist() const {
	return dist ;
}

void NodeInfo::set_tDesc (unsigned int tDesc){
	this->tDesc = tDesc;
}
void NodeInfo::set_tFin (unsigned int tFin){
	this->tFin = tFin ;
}
void NodeInfo::set_nNodeIndex (unsigned int nNodeIndex){
	this->nNodeIndex = nNodeIndex ;
}
void NodeInfo::set_dist (unsigned int dist){
	this->dist = dist ;
}
void NodeInfo::set_color(Color color){
	this->color = color ;
}




class Graph{
private:
	Node * nodes ;
	int n ;
public:
	Graph(int n);
	~Graph();
	std::vector<int> bfs(int node);
	void dfs(int node);
	void addEdge(int u,int v,EDGE_DIRECTION dir);
	void printPretty();
	bool isBipartite();
	void sortNeigh();
	void sortTopological(int node);

};



NodeInfo::NodeInfo()
{
	color = WHITE;
	dist = -1;
	tDesc = 0;
	tFin = 0;
	nNodeIndex = -1;
	parent = -1; 
}

std::ostream& operator<<(std::ostream& out,Node& node)
{
	auto content = node.get_neigh();
	for(auto it = content.begin();it!=content.end();++it){
		out << *it << " ";
	}

		
	out<<std::endl;
	
	return out;
	
}
std::ostream& operator<<(std::ostream& out,const std::vector<int>& content)
{
	
	for(auto it = content.begin();it!=content.end();++it){
		out << *it << " ";
	}

		
	out<<std::endl;
	
	return out;
	
}

Graph::Graph(int n){
	this->n = n ; 
	nodes = new Node[n];
}

Graph::~Graph(){
	delete[] nodes ;
}

void Graph::addEdge(int u,int v,EDGE_DIRECTION dir){
	nodes[u].add_neighbour(v);

	if(dir == BIDIRECTIONAL){
		nodes[v].add_neighbour(u);
	}
}

void Graph::sortNeigh()
{

	for (int i=0;i<n;i++){
		
	   	nodes[i].sort();
	 
	}
}

std::vector<int> Graph::bfs(int node)
{
	std::vector<NodeInfo> nodeInfos(n);
	std::queue<int> Q ;
		
	//std::cout<<"BFS Traversing from node "<<node<<std::endl;
	
	//initializari
	int i = 0 ;
	for(auto it = nodeInfos.begin();it !=  nodeInfos.end() ; ++it){
		it->set_nNodeIndex(i++);
		it->set_parent(-1);

	}

	nodeInfos[node].set_color(GRAY);
	nodeInfos[node].set_dist(0);

	Q.push(node);

	while(!Q.empty()){
		int v = Q.front();
		//std::cout << v << "->";
		Q.pop();
		std::vector<int> & neigh = nodes[v].get_neigh() ;

		for(auto it = neigh.begin();it != neigh.end() ; ++it){
				if(nodeInfos[*it].get_color() == WHITE ){

				nodeInfos[*it].set_color(GRAY);

				nodeInfos[*it].set_parent(v);

				nodeInfos[*it].set_dist(nodeInfos[v].get_dist() + 1);

				Q.push(*it);

			}
			
		}

		nodeInfos[v].set_color(BLACK);
	}
	
	std::vector<int> to_return ;

	for(int i = 1 ; i < nodeInfos.size() ; ++i)
		to_return.push_back(nodeInfos[i].get_dist());
//	std::cout<<std::endl;		

	return to_return;
}



int main(){
	std::ifstream in; 
   	in.open("bfs.in"); 	

   	int vertex , edges , source ;
   	in >> vertex ;
   	in >> edges ;
   	in >> source ;

   	Graph graf(vertex + 1);

   	for(int i = 0 ; i < edges ; ++i){
   		int u , v ;
   		in >> u ;
   		in >> v ;
 		graf.addEdge(u,v,UNIDIRECTIONAL);
   	}
   	in.close();
   	graf.sortNeigh();

   	auto result = graf.bfs(source);

   	std::ofstream out; 
   	out.open("bfs.out"); 	

   	for(int i = 0 ; i < result.size() ; ++ i ){
   		out << result.at(i) << " ";
   	}
   	
   	out.close();

	return 0 ; 
}