#include <fstream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

class Graph{
private:
	const unsigned int number_of_edges_;
	const unsigned int number_of_vertices_;
	vector<unsigned int>* edges_;

public:
	Graph(unsigned int number_of_vertices, unsigned int number_of_edges) 
	: number_of_vertices_(number_of_vertices), number_of_edges_(number_of_edges) {
		edges_ = new vector<unsigned int>[number_of_vertices_ + 1];
	}

	void addEdge(unsigned int source, unsigned int destination) {
		edges_[source].push_back(destination);
	}

	void calculateDistance(unsigned int source, unsigned int distances[]) {
		queue<unsigned int> path;

		memset(distances, 0, sizeof(distances));

		unsigned int vertex = source;

		path.push(source);

		while (!path.empty()) {

			for (int neighbour = 0; neighbour < edges_[vertex].size(); neighbour++) {
				if (!distances[edges_[vertex][neighbour]] && vertex != source) {
					path.push_back(edges_[vertex][neighbour]);
					distances[edges_[vertex][neighbour]] = distances[vertex] + 1;
				}
			}

			vertex = path.front();
			path.pop();
		}
	}

	~Graph() {
		delete[] edges_;
	}
};

int main() {
	ifstream in("bfs.in");
	ofstream out("bfs.out");
	int n, m, s;

	in>>n>>m>>s;

	Graph graph(n,m);
	int a,b;

	for (int i = 1; i <= m; i++) {
		in>>a>>b;
		graph.addEdge(a,b);
	}

	unsigned int distances[n+1];

	graph.calculateDistance(s, distances);
	
	for (int i = 1; i <= n; ++i)
		if (i != s && distances[i] == 0) {
			out<<"-1 ";
		} else {
			out<<distances[i]<<" ";
		}

	return 0;
}