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

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


int dist[100001];

int main(){
	queue<int> q;
	int n, m, x, y, s;


	
	fin >> n >> m >> s;
	q.push(s);
	dist[s] = 0;
	vector< vector<int> > g(n+1);

	fill(dist+1, dist+n+1, -1);
	for(int i = 0; i < m; i++){
		fin >> x >> y;

		g[x].push_back(y);
	}

	dist[s]=0;
	while(!q.empty()){
		x = q.front();
		q.pop();

		for(int nod : g[x]){
			if(dist[nod]==-1){
				dist[nod] = dist[x]+1;
				q.push(nod);
			}
		}	
	}


	for(int i = 1; i <= n; i++){
		fout << dist[i] << " ";
	}


	return 0;
}