#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

bool sortingCriteria(pair<int, int> firstPair, pair<int, int> secondPair) {
	if (firstPair.first != secondPair.first)
		return firstPair.first < secondPair.first;
	return firstPair.second < secondPair.second;
}

bool comparePairs(pair<int, int> fPair, pair<int, int> sPair) {
	if (fPair.first == sPair.first && fPair.second == sPair.second)
		return true;
	return false;
}

bool binarySearch(vector<pair<int, int>>& pairs, pair<int, int>& wanted, int left, int right) {
	int middle;
	while (left <= right) {
		middle = (left + right) / 2;
		if (comparePairs(pairs[middle], wanted))
			return true;
		if (pairs[middle].first == wanted.first) {
			if (pairs[middle].second < wanted.second)
				return binarySearch(pairs, wanted, middle + 1, right);
			return binarySearch(pairs, wanted, left, middle - 1);
		}
		else {
			if(pairs[middle].first < wanted.first)
				return binarySearch(pairs, wanted, middle + 1, right);
			return binarySearch(pairs, wanted, left, middle - 1);
		}
	}
	return false;
}

void BFS(vector<pair<int, int>>& pairs, vector<int>& visited, int& X, int& N) {
	int pairsLength = pairs.size();
	queue<int> nodes;
	nodes.push(X);
	++visited[X - 1];
	while (!nodes.empty()) {
		int node = nodes.front();
		nodes.pop();
		for (int i = 1; i <= N; ++i) {
			pair<int, int> wanted;
			wanted.first = node;
			wanted.second = i;
			if (binarySearch(pairs, wanted, 0, pairsLength - 1))
				if (visited[i - 1] == -1) {
					visited[i - 1] = visited[node - 1] + 1;
					nodes.push(i);
				}
		}
	}
}

int main() {
	ifstream fin("bfs.in");
	ofstream fout("bfs.out");
	int N, M, X;
	fin >> N >> M >> X;
	vector<pair<int, int>> arches;
	vector<int> visited(N, -1);
	int x, y;
	for (int i = 0; i < M; ++i) {
		fin >> x >> y;
		pair<int, int> pairNodes;
		pairNodes.first = x;
		pairNodes.second = y;
		arches.push_back(pairNodes);
	}
	sort(arches.begin(), arches.end(), sortingCriteria);
	BFS(arches, visited, X, N);
	for (int i = 0; i < N; ++i)
		fout << visited[i] << " ";
	return 0;
}