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

using namespace std;

vector<int> *adj;
int *v, verticesNumber, edgeNumber, sourceNode;

void bfs(int s);
void addEdge(int, int);
int main(){


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

	read>>verticesNumber>>edgeNumber>>sourceNode;

	adj = new vector<int>[verticesNumber];
	v = new int[verticesNumber];

	for(int i=0; i<verticesNumber; i++)
		v[i] = -1;

	for(int i=0; i<edgeNumber; i++){

		int x,y;
		read>>x>>y;
		x--;
		y--;
		addEdge(x, y);
	}

	bfs(sourceNode-1);

	for(int i=0; i<verticesNumber; i++)
		write<<v[i]<<" ";
	
	return 0;
}

void bfs(int s){

	bool *visited = new bool[verticesNumber];

	for(int i=0; i<verticesNumber; i++)
		visited[i] = false;

	queue<int> Q;

	visited[s] = true;
	v[s] = 0;

	Q.push(s);

	while(!Q.empty()){

		s = Q.front();
		Q.pop();

		vector<int>::iterator it = adj[s].begin();

		for(; it!=adj[s].end(); ++it){
			if(!visited[*it]){
				visited[*it] = true;

				v[*it] = v[s] + 1;

				Q.push(*it);
			}
		}
	}


}

void addEdge(int v, int w){
	adj[v].push_back(w);
}