#include <fstream>
#include <list>
#include <vector>
#include <unordered_set>

class Graph {
	int V;
	std::list<int> *adj;

public:
	Graph(int V);
	void addDirectedEdge(int s, int d);

	/* Breadth First Search */
	void BreadthFirstSearch(int sourceNode);
};

Graph::Graph(int V) {
	this->V = V;
	adj = new std::list<int>[V];
}

void Graph::addDirectedEdge(int s, int d) {
	adj[s].push_back(d);
}

void Graph::BreadthFirstSearch(int sourceNode) {
	std::vector<int> distanceFromSource(V, 0);
	std::vector<bool> discovered(V, false);
	// discovered.resize(V, false);

	std::list<int> Q;
	Q.push_back(sourceNode);
	discovered[sourceNode] = true;

	while (!Q.empty()) {
		int nodeToProcess = Q.front();
		Q.pop_front();
		for (auto it = adj[nodeToProcess].begin(); it != adj[nodeToProcess].end(); it++) {
			if (!discovered[*it]) {
				distanceFromSource[*it] = distanceFromSource[nodeToProcess] + 1;
				discovered[*it] = true;
				Q.push_back(*it);
			}
		}
	}

	std::ofstream fout("bfs.out");
	for (int i = 0; i < V; i++) {
		if (!discovered[i])
			distanceFromSource[i] = -1;
		fout << distanceFromSource[i] << " ";
	}
}

struct pairHash {
public:
	template <typename T, typename U>
	std::size_t operator()(const std::pair<T, U> &x) const
	{
		return std::hash<std::size_t>()(std::hash<T>()(x.first)*3 + std::hash<U>()(x.second));
	}
};

int main(void) {
	int N, M, Source, s, d;
	std::ifstream fin("bfs.in");
	fin >> N >> M >> Source;

	std::unordered_set<std::pair<int, int>, pairHash> edgesInserted;
	Graph graph = Graph(N);
	for (; M > 0; M--) {
		fin >> s >> d;
		if (edgesInserted.empty() || edgesInserted.find(std::pair<int, int>(s - 1, d - 1)) == edgesInserted.end()) {
			graph.addDirectedEdge(s - 1, d - 1);
			edgesInserted.insert(std::pair<int, int>(s - 1, d - 1));
		}
	}

	graph.BreadthFirstSearch(Source - 1);
	return 0;
}