#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];
muchie c[1000001];

int cb(int nod)
{
	int st = 0;
	int dr = m;
	int p = 0;

	while (st <= dr)
	{
		int mij = (st + dr) / 2;

		if (lmuchi[mij].a >= nod)
		{
			dr = mij - 1;
			p = mij;
		}
		else
		{
			st = mij + 1;
		}
	}

	return p;
}

	
void interclasare(muchie a[], muchie b[], int nst, int ndr)
{
	int i = 0;
	int j = 0;
	int k = 0;

	while (i < nst && j < ndr)
	{
		if (a[i].a < b[j].a)
		{
			c[k].a = a[i].a;
			c[k].b = a[i].b;
			i++;
			k++;
		}
		else if (a[i].a > b[j].a)
		{
			c[k].a = b[j].a;
			c[k].b = b[j].b;
			j++;
			k++;
		}
		else
		{
			if (a[i].b < b[j].b)
			{
				c[k].a = a[i].a;
				c[k].b = a[i].b;
				i++;
				k++;
			}
			else
			{
				c[k].a = b[j].a;
				c[k].b = b[j].b;
				j++;
				k++;
			}
		}
	}

	while (i < nst)
	{
		c[k].a = a[i].a;
		c[k].b = a[i].b;
		k++;
		i++;
	}
	while (j < ndr)
	{
		c[k].a = b[j].a;
		c[k].b = b[j].b;
		j++;
		k++;
	}
}

void mergesort(muchie* a, int n)
{
	if (n <= 1)
	{
		return;
	}

	int mij = n / 2;
	int nrelemst = mij;
	int nrelemdr = mij + n % 2;
	
	muchie* st = a + 0;
	muchie* dr = a + mij;

	mergesort(st, nrelemst);
	mergesort(dr, nrelemdr);

	interclasare(st, dr, nrelemst, nrelemdr);

	for (int y = 0; y < n; y++)
	{
		a[y].a = c[y].a;
		a[y].b = c[y].b;
	}

}

bool valid(int a, int b)
{
	if (cb(a))
	{
		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];
		int poz = cb(ncurent);
		
		for (int i = poz; lmuchi[i].a == ncurent; i++)
		{
			int x = lmuchi[i].b;

			if (nvizitat[x] == 0)
			{
				nvizitat[x] = 1;
				coada[l] = x;
				l++;
				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);

	mergesort(lmuchi, m);

	bfs(x, n);

	afisare(n);
}