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

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