#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "bfs.in"
#define FOUT "bfs.out"
#define MAX_N 100005
#define ret 100000

typedef struct NOD
{
	int nod;
	NOD *next;
};

NOD *A[MAX_N];
int D[MAX_N];
int C[MAX_N];
int V[MAX_N];

int N, M, S;

	void readdata ()
	{
		int x, y, i;
		scanf ("%d %d %d", &N, &M, &S);
		for (i = 1; i <= M; ++i)
		{
			scanf ("%d %d", &x, &y);	
			NOD *q = new (NOD);
			q->nod = y, q->next = A[x], A[x] = q;	
		}
	}

	void BFS ()
	{
		int li, lf, nod;
		memset (D, 0x3ff, sizeof (D));
		D[S] = 0;

		li = lf = 0, C[++lf] = S, V[S] = 1;

		while (li != lf)
		{	
			nod = C[(++li) % ret];
			for (NOD *q = A[nod]; q != NULL; q = q->next)
				if (!V[q->nod])
				{
					V[q->nod] = 1;
					C[(++lf) % ret] = q->nod;
					D[q->nod] = D[nod] + 1;
				}
		}

		int i;
		for (i = 1; i <= N; ++i) printf ("%d ", D[i]);
	}

	int main ()
	{
		freopen (FIN, "r", stdin);
		freopen (FOUT, "w", stdout);
		
		readdata ();
		BFS ();

		return 0;
	}