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

enum NodeState {
	NOT_VISITED, VISITED
};

struct Node {
	std::vector<int> neighbours;
};

Node graph[100001];
int cost[100010];
std::queue<int> toBeProcessed;
int m, n, a, b, s;
std::ifstream fin("bfs.in");
std::ofstream fout("bfs.out");

void computeNeighboursCosts(int currentNode)
{
	for (auto node : graph[currentNode].neighbours) {
		if (cost[node] == -1) {
			cost[node] = cost[currentNode] + 1;
			toBeProcessed.push(node);
		}
	}
}

void calculateCosts()
{
	while (!toBeProcessed.empty()) {
		int currentNode = toBeProcessed.front();

		computeNeighboursCosts(currentNode);

		toBeProcessed.pop();
	}
}

void bfs(int startIndex) {

	std::fill(cost + 1, cost + n + 1, -1);
	
	cost[startIndex] = 0;
	toBeProcessed.push(startIndex);

	calculateCosts();
}

int main() {
	fin >> n >> m >> s;

	for (int i = 0; i < m; i++) {
		fin >> a >> b;

		graph[a].neighbours.push_back(b);
	}

	bfs(2);

	for (int i = 1; i <= n; i++) {
		fout << cost[i] << ' ';
	}

	return 0;
}