#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <iterator>

using namespace std;

struct Node {
	list<int> adjacentNodesIds;
};

class Graph {
public:
	Graph(const char *filename);
	vector<int> calculateDistancesFromSourceNodeToAllNodes();
private:
	void visitAllAdjacentNodesOf(int nodeId);
	void visitNode(int nodeToVisit, int nodeThatVisits);
	vector<Node> nodes;
	queue<int> nodesToVisitIds;
	int sourceNodeId;
	vector<int> distances;
	vector<bool> visitedNodesIds;
};

Graph::Graph(const char *filename) {
	ifstream fin(filename);
	int n, m;
	fin >> n >> m >> sourceNodeId;
	nodes = vector<Node>(n+1);
	for (int i = 0; i < m; ++i) {
		int x, y;
		fin >> x >> y;
		nodes[x].adjacentNodesIds.push_back(y);
	}
	fin.close();
}

vector<int> Graph::calculateDistancesFromSourceNodeToAllNodes() {
	distances = vector<int>(nodes.size(), -1);
	visitedNodesIds = vector<bool>(nodes.size(), false);
	visitedNodesIds[sourceNodeId] = true;
	distances[sourceNodeId] = 0;
	nodesToVisitIds.push(sourceNodeId);
	while (!nodesToVisitIds.empty()) {
		int currentNodeToVisitId = nodesToVisitIds.front();
		nodesToVisitIds.pop();
		visitAllAdjacentNodesOf(currentNodeToVisitId);
	}

	return distances;
}

void Graph::visitAllAdjacentNodesOf(int nodeId) {
	list<int>::iterator adjacentNodesIterator;
	adjacentNodesIterator = nodes[nodeId].adjacentNodesIds.begin();
	while (adjacentNodesIterator != nodes[nodeId].adjacentNodesIds.end()) {
		if (!visitedNodesIds[*adjacentNodesIterator]) {
			visitNode(*adjacentNodesIterator, nodeId);
			nodesToVisitIds.push(*adjacentNodesIterator);
		}
		++adjacentNodesIterator;
	}
}

void Graph::visitNode(int nodeToVisit, int nodeThatVisits) {
	visitedNodesIds[nodeToVisit] = true;
	distances[nodeToVisit] = distances[nodeThatVisits] + 1;
}

int main() {
	Graph graph("bfs.in");
	vector<int> distances = graph.calculateDistancesFromSourceNodeToAllNodes();
	ofstream fout("bfs.out");
	for (int i = 1; i < distances.size() - 1; ++i) {
		fout << distances[i] << " ";
	}
	fout << distances[distances.size() - 1] << '\n';
	fout.close();
	return 0;
}