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

using namespace std;

struct Node {
	list<int> adjacentNodes;
};

class Graph {
public:
	Graph(const char *filename);
	vector<int> calculateDistancesFromSourceNodeToAllNodes();
private:
	void setupStateForTraversal();
	void visitAdjacentNodesOf(int rootNode);
	void visitNode(int visitedNode, int visitorNode);
	vector<Node> nodes;
	vector<int> distances;
	vector<bool> visitedNodes;
	queue<int> rootNodes;
	int sourceNode;
};

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

vector<int> Graph::calculateDistancesFromSourceNodeToAllNodes() {
	setupStateForTraversal();
	while (!rootNodes.empty()) {
		int currentRootNode = rootNodes.front();
		rootNodes.pop();
		visitAdjacentNodesOf(currentRootNode);
	}
	return distances;
}

void Graph::setupStateForTraversal() {
	distances = vector<int>(nodes.size(), -1);
	visitedNodes = vector<bool>(nodes.size(), false);
	distances[sourceNode] = 0;
	visitedNodes[sourceNode] = true;
	rootNodes.push(sourceNode);
}

void Graph::visitAdjacentNodesOf(int rootNode) {
	list<int>::iterator adjacentNodesIterator;
	adjacentNodesIterator = nodes[rootNode].adjacentNodes.begin();
	while (adjacentNodesIterator != nodes[rootNode].adjacentNodes.end()) {
		if (visitedNodes[*adjacentNodesIterator] == false) {
			visitNode(*adjacentNodesIterator, rootNode);
			rootNodes.push(*adjacentNodesIterator);
		}
		++adjacentNodesIterator;
	}
}

void Graph::visitNode(int visitedNode, int visitorNode) {
	visitedNodes[visitedNode] = true;
	distances[visitedNode] = distances[visitorNode] + 1;
}

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