#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int nvizitat[100001] = { 0 };
int coada[100001] = { 0 };
int drum[100001] = { 0 };

int m = 0;
struct muchie
{
	int a;
	int b;
};

muchie lmuchi[1000001];

bool valid(int a, int b)
{
	for (int y = 0; y < m; y++)
	{
		if (lmuchi[y].a == a && lmuchi[y].b == b)
		{
			return true;
		}
	}
	return false;
}

void citire(int m, int n)
{
	int i = 0;
	int j = 0;

	for (int x = 0; x < m; x++)
	{
		fin >> i >> j;
		lmuchi[x].a = i;
		lmuchi[x].b = j;
	}
	for (int x = 1; x <= n; x++)
	{
		drum[x] = -1;
	}
}

int l = 0;

void bfs(int k, int n)
{
	nvizitat[k] = 1;

	coada[l] = k;
	l++;

	drum[k] = 0;

	int index = 0;

	while (index < l)
	{
		int ncurent = coada[index];
		for (int x = 1; x <= n; x++)
		{
			if (valid(ncurent,x))
			{
				if (nvizitat[x] == 0)
				{
					coada[l] = x;
					l++;
					nvizitat[x] = 1;
					drum[x] = drum[ncurent] + 1;
				}
			}
		}
		index++;
	}
}

void afisare(int n)
{
	for (int x = 1; x <= n; x++)
	{
		fout << drum[x] << " ";
	}
}

int main()
{
	int n = 0;
	int x = 0;

	fin >> n >> m >> x;

	citire(m,n);

	bfs(x, n);

	afisare(n);
}