#include <stdio.h>
#include <queue>
using namespace std;
queue <int> c;
#define n 100000
#define m 1000000
int N , M , S;
int drum[n];
int viz[n];
struct arc
{
	int x,y;
}a;

arc sir[m];
void golire()
{
	for (int i = 1 ; i <= N ; ++i)
		drum[i] = -1;
}
int primul;
int nrarce;
int ok = 0;
int main()
{
	freopen ("bfs.in","r",stdin);
	freopen ("bfs.out","w",stdout);
	scanf ("%d %d %d\n" , &N , &M , &S);
	c.push(S);
	golire();
	viz[S] = 1;
	drum[S] = 0;
	for (int i = 0 ; i < M ; ++i)
	{
		scanf ("%d %d\n" , &a.x , &a.y);
		sir[i] = a;
	}
	
	int j = 0;
	int nod = 0;
	nod = c.front();
	nrarce = 1;
	while (!c.empty())
	{
		
		while (j < M)
		{
			if (sir[j].x == nod)
			{
				while (sir[j].x == nod)
				{

					if (!viz[sir[j].y])
					{
						primul = c.front();
						c.push(sir[j].y);
						drum[sir[j].y] = nrarce;
						viz[sir[j].y] = 1;
						ok = 1;
					}
					
					++j;
				}
			}
			else
				++j;
		}
		if (c.front() == primul)
			nrarce++;
		c.pop();
		if (!c.empty())
			nod = c.front();
		
		j = 0;
		//if (ok == 1)
		//	nrarce++;
		ok = 0;
	}
	
	for (int i = 1 ; i <= N ; ++i)
		printf("%d ",drum[i]);
	return 0;
}