#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <tr1/unordered_map>
#include <sstream>

using namespace std;
using namespace tr1;

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

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

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

string convertInt(int number)
{
   stringstream ss;//create a stringstream
   ss << number;//add number to the stream
   return ss.str();//return a string with the contents of the stream
}

void bf(){
	string currentnode;
	int currentdistance;
	queue <string> coada;
	vector <string> neighbours;
	vector <string>::iterator it;
	coada.push(source);
	int i;
	for(i=1;i<=n;++i){
		result[convertInt(i)]=-1;
	}
	result[source]=0;
	visited[source]=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[convertInt(i)]<<" ";
	}
}

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