#include <fstream>
#include <vector>
#include <queue>
#include <list>
using namespace std;

void BFS(vector<list<unsigned> >& adjList,
		vector<int>& distances,
		unsigned source) {

	queue<unsigned> q;
	q.push(source);
	distances[source] = 0;

	list<unsigned>::iterator it;
	unsigned current;
	while(!q.empty()) {
		current = q.front();
		q.pop();

		for(it = adjList[current].begin(); it != adjList[current].end(); it++) {
			if(distances[*it] == -1) {
				distances[*it] = distances[current] + 1;
				q.push(*it);
			}
			else
				if(distances[*it] > distances[current] + 1) {
					distances[*it] = distances[current] + 1;
					q.push(*it);
				}
		}
	}
}

int main() {
	ifstream inStr("bfs.in");
	ofstream outStr("bfs.out");

	unsigned numNodes, numEdges, source;
	inStr >> numNodes >> numEdges >> source; source--;

	vector<list<unsigned> > adjList(numNodes);
	vector<int> distances(numNodes, -1);

	unsigned from, to;
	for(unsigned i=0; i < numEdges; i++) {
		inStr >> from >> to;
		adjList[--from].push_back(--to);
	}

	BFS(adjList, distances, source);

	for(unsigned i=0; i < numNodes; i++)
		outStr << distances[i] << ' ';
	outStr << "\n";

	return 0;
}