// Bfs.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string.h>

using namespace std;

vector<int> graph[100000];
bool visited[1000000];
int cost[100000];

void bfs_comp(int source,int n)
{
	memset(visited, 0, (n + 1)*sizeof(bool));
	memset(cost, -1, (n + 1)*sizeof(int));

	cost[source] = 0;
	queue<int> Q;
	Q.push(source);
	visited[source] = true;

	while (!Q.empty())
	{
		int head = Q.front();
		for (int i : graph[head])
		{
			if (!visited[i])
			{
				visited[i] = true;
				Q.push(i);
				cost[i] = cost[head] + 1;
			}
		}

		Q.pop();
	}
}

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

	int N, M, S,x,y;

	in >> N >> M >> S;
	for (int i = 0; i < M; i++)
	{
		in >> x;
		in >> y;
		graph[x].push_back(y);
	}

	bfs_comp(S,N);

	for (int i = 1; i <= N; i++)
	{
		out << cost[i] << " ";
	}

	return 0;
}