// 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>

#define BYTE unsigned byte
using namespace std;

vector<int> *graph;
bool *visited;
int *cost;

void init(int n)
{
	graph = new vector<int>[n + 1];
	visited = new bool[n + 1];
	cost = new int[n + 1];

	memset(visited, 0, (n + 1)*sizeof(bool));
	memset(cost, -1, (n + 1)*sizeof(int));
}


void bfs_comp(int source,int n)
{
	
	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;
	init(N);
	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;
}