#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

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, int distances[]) {
		queue<unsigned int> path;

		for (int i = 1; i <= number_of_vertices_; i++)
			distances[i] = -1;

		unsigned int vertex = source;
		distances[source] = 0;

		path.push(source);

		while (!path.empty()) {

			for (int neighbour = 0; neighbour < edges_[vertex].size(); neighbour++) {
				if (distances[edges_[vertex][neighbour]] ==-1) {
					path.push(edges_[vertex][neighbour]);
					distances[edges_[vertex][neighbour]] = distances[vertex] + 1;
				}
			}

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

	~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);
	}

	int distances[n+1];

	graph.calculateDistance(s, distances);
	
	for (int i = 1; i <= n; ++i)
			out<<distances[i]<<" ";
		

	return 0;
}