# include <fstream>
# include <vector>
# include <queue>
using namespace std;

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

queue <int> Q;
vector <int> v[100010];
int n, m, S, i, x, y, sol[100010];

void make (){
	Q.push (S);
	for (; !Q.empty (); Q.pop ()){
		int val = Q.front ();
		int siz = v[val].size ();
		for (int k = 0; k < siz; ++k){
			int nr = v[val][k];
			if (!sol[nr]){
				Q.push (nr);
				sol[nr] = sol[val] + 1;
			}
		}
	}
}
int main (){
	f >> n >> m >> S;
	
	for (i = 1; i <= m; ++i){
		f >> x >> y;
		v[x].push_back (y);
	}
	
	sol[S] = 1;
	make ();
	
	for (i = 1; i <= n; ++i)
		g << sol[i] - 1 << ' ';
	
	g.close ();
	return 0;
}