// http://infoarena.ro/problema/bfs
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

int nodes,edges,startNode;
vector< list<int> > graph;
vector<int> dist;	// numarul de arce (se considera costul 1)
vector<int> cost;
queue<int> myQueue;

void read();
void breadthFirst(int startNode);
void write();

int main() {
	read();
	breadthFirst(startNode);
	write();

	return (0);
}

void read() {
	ifstream in("bfs.in");
	int from,to;

	in >> nodes >> edges >> startNode;
	graph.resize(nodes+1);
	dist.resize(nodes+1);
	cost.resize(nodes+1);

	for(int i=1;i<=edges;i++) {
		in >> from >> to;
		graph.at(from).push_back(to);
	}

	in.close();
}

void breadthFirst(int startNode) {
	int node;

	cost.at(startNode) = true;
	for(list<int>::iterator it=graph.at(startNode).begin();it!=graph.at(startNode).end();it++) {
		myQueue.push(*it);
	}

	while(!myQueue.empty()) {
		node = myQueue.front();
		myQueue.pop();

		for(list<int>::iterator it=graph.at(node).begin();it!=graph.at(node).end();it++) {
			if(!cost.at(*it)) {
				myQueue.push(*it);
				cost.at(*it) = cost.at(node) + 1;
			}
		}
	}

}

void write() {
	ofstream out("bfs.out");

	for(int i=1;i<=nodes;i++)
		out << cost.at(i) - 1 << " ";
	out << "\n";

	out.close();
}