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

///// DESCRIPTION
// THIS PROGRAM EMPLOYS BREADTH-FIRST SEARCH
// ON AN INPUT OF A DIRECTED GRAPH
// WITH N VERTICES AND M EDGES
// TO DETERMINE THE MINIMUM NUMBER
// OF EDGES NEEDED TO REACH NODE X 
// FROM A GIVEN NODE S
/////

typedef struct nodeCost { 
	int node; int cost; 
	} NodeCost;

int main(int argc, char **argv)
{
	// INPUT DATA
	ifstream indata("bfs.in");
	int n, m, s;
	indata >> n >> m >> s;
	
	vector<int> edges[n + 1];
	for (int i = 0, a, b; i < m; i++) {
		indata >> a >> b;
		edges[a].push_back(b);
	}
	
	indata.close();
	
	// RUN BFS
	int edgeCost[n + 1];	
	bool visited[n + 1];
	for (int i = 1; i <= n; i++) {
		visited[i] = false;
		edgeCost[i] = -1;
	}
	
	deque<NodeCost> nodesToVisit;
	nodesToVisit.push_back((NodeCost) { s, 0 });
	visited[s] = true;
	
	while(nodesToVisit.empty() == false) {
		NodeCost currentNode = nodesToVisit.front();
		edgeCost[currentNode.node] = currentNode.cost;
		nodesToVisit.pop_front();
		
		vector<int>::iterator vit = edges[currentNode.node].begin();
		while(vit != edges[currentNode.node].end()) {
			if (visited[*vit] == false) {
				nodesToVisit.push_back((NodeCost) { *vit, currentNode.cost + 1 });
				visited[*vit] = true;
			}
			vit++;
		}
	}
	
	// OUTPUT DATA
	ofstream outdata("bfs.out");
	for (int i = 1; i <= n; i++) {
		outdata << edgeCost[i] << " ";
	}
	outdata.close();
	
	return 0;
}