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

/*enum COLOR
{
	WHITE, GREY, BLACK
};*/

//std::vector<COLOR> color;
//std::list<int> topologicSortedNodes;
std::vector<int> distanceFromSource;
std::vector<bool> discovered;

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

	//void explore(int node);

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

	/* Topological Sort */
	//void TopologicalSort();

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

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

void Graph::addUndirectedEdge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

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

/*void Graph::TopologicalSort() {

	for (int i = 0; i < V; i++) {
		if (color[i] == WHITE) {
			explore(i);
		}
	}
}

void Graph::explore(int node) {
	color[node] = GREY;

	for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
		if (color[*it] == WHITE) {
			color[*it] = GREY;
			explore(*it);
		}
	}

	color[node] = BLACK;
	topologicSortedNodes.push_front(node + 1);
}*/

void Graph::BreadthFirstSearch(int sourceNode) {
	distanceFromSource.resize(V, 0);
	//color.resize(V, WHITE);
	discovered.resize(V, false);

	std::list<int> Q;
	Q.push_back(sourceNode);
	//color[sourceNode] = GREY;
	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 (color[*it] == WHITE) {
			if (!discovered[*it]) {
				distanceFromSource[*it] = distanceFromSource[nodeToProcess] + 1;
				//color[*it] = GREY;
				discovered[*it] = true;
				Q.push_back(*it);
			}
		}
		//color[nodeToProcess] = BLACK;
	}
}

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

	Graph graph = Graph(N);
	for (; M > 0; M--) {
		fin >> s >> d;
		graph.addDirectedEdge(s - 1, d - 1);
	}

	graph.BreadthFirstSearch(Source - 1);

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