#include <fstream>
#include <string.h>
#include <iostream>
#include <cstdlib>
#include <queue>
#include <stack>
#include <math.h>
#define max 100000
using namespace std;
struct node{
	int neighb[max];
	int k, dist;	// k - size(neighb), dist = distanta fata de radacina
	bool visited;
};
int number_of_nodes, number_of_edges, source;
void bfs(node nod[]){

	int i, elem, neigb, d = 0;
	ofstream fout("bfs.out");
	queue<int> myqueue;
	myqueue.push(source);
	nod[source].visited = true;
	nod[source].dist = 0;
	while(!myqueue.empty()){
		elem = myqueue.front();
		myqueue.pop();
		for(int i = 0; i < nod[elem].k; i++){
			neigb = nod[elem].neighb[i];
			if(nod[neigb].visited != true){
				nod[neigb].dist = nod[elem].dist+1;
				//cout<<neigb+1<<" "<<d<<"\n";
				nod[neigb].visited = true;
				myqueue.push(neigb);
			}
		}
		// 2-> 1 2 5
		// 1 -> 2
		// 5 -> 3
	}
	for(i = 0; i < number_of_nodes; i++){
		fout<<nod[i].dist<<" ";
	}
}
int main(){
	
	int nod1, nod2, i;
	ifstream fin("bfs.in");
	fin>>number_of_nodes>>number_of_edges>>source;
	source--;
	node nod[number_of_nodes];
	for(i = 0; i < number_of_nodes; i++){
		nod[i].k = 0;
		nod[i].visited = false;
		nod[i].dist = -1;
	}
	for (i = 0; i < number_of_edges; i++){
		fin>>nod1>>nod2;
		nod[nod1-1].neighb[nod[nod1-1].k] = nod2-1;
		nod[nod1-1].k++;
	}
	bfs(nod);
	
	return 0;
}