#define oo (1<<31-1)
#define NULL 0

template <typename T>
struct node {
		T value;
		node *next;
		node (T val): value(val) {
			next = NULL;
		}
};
	
template <typename T>
class Queue {
	node <T> *first, *last;
public:
	Queue () { 
		first = last = NULL;
	}
	void push(T &val) {
		node<T> *p = new node<T> (val);
		if(first == NULL)
			first = last = p;
		else {
			last->next = p;
			last = p;
		}
	}
	T pop() {
		node<T> *p = first;
		T aux = first -> value;
		
		first = first -> next;
		delete p;
		return aux;
		
	}
	bool empty() {
		return (first == NULL);
	}
};

#include <vector>
class Graph {
	int size;
	std::vector <int> *v;
	std::vector <int> dist;
	std::vector <int> seen;
	
public:
	Graph(unsigned int s): size(s), dist(s,oo), seen(s,false) {
		v = new std::vector <int> [s];
	}
	void addEdge(int i, int j) {
		v[i].push_back(j);
	}
	std::vector <int> * bfs(int root) {
		Queue <int> q; 
		q.push(root);
		dist[root] = 0;
		
		int x, i;
		while(!q.empty()) {
			x = q.pop();
			for(i=0; i<v[x].size(); i++) {
				if(dist[v[x][i]] == oo) {
					dist[v[x][i]] = dist[x] + 1;
					q.push(v[x][i]);
				}
			}
		}
		return &dist;
	}
};

#include <fstream>
std::ifstream f("bfs.in");
std::ofstream g("bfs.out");
int main() {
	int n, m, x, y, r;
	f>>n>>m>>r;
	Graph G(n+1);
	
	while(m--) {
		f>>x>>y;
		G.addEdge(x,y);
	}
	
	std::vector <int> *res = G.bfs(r);
	for(int i=1; i<res->size(); i++)
		if((*res)[i] == oo) g<<-1<<' ';
		else g<<(*res)[i]<<' ';
		
}