#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

#define nmax 100005

using namespace std;


int n, m, s;
vector <int> L [nmax];
vector <int> V (nmax, -1);
queue <int> Q;

void scan ()
{
	int i, x, y;
	scanf ("%d%d%d", &n, &m, &s);
	for (i=1; i<=m; ++i)
	{
		scanf ("%d%d", &x, &y);
		L [x].push_back (y);
	}
}

void bfs ()
{
	int p;
	Q.push (s);
	V [s]=0;
	while (!Q.empty ())
	{
		p=Q.front ();
		vector <int>::iterator it;
		for (it=L [p].begin (); it != L [p].end (); ++it)
			if (V [*it] == -1)
			{
				V [*it]=V [p]+1;
				Q.push (*it);
			}	
		Q.pop ();
	}
}

void print ()
{
	int i;
	for (i=1; i<=n; ++i)
		printf ("%d ", V [i]);
	printf ("\n");
}

int main ()
{
	freopen ("bfs.in", "r", stdin);
	freopen	("bfs.out", "w", stdout);
	scan ();
	bfs ();
	print ();
	return 0;
}