#include <stdio.h>
#include <stdlib.h>

int N, M, S;


#define SIZE 100005

struct nod 
{
	int dest;
	struct nod * next;
};

struct nod * noduri[SIZE];

int VIZ[SIZE], DIST[SIZE], Q[SIZE];

int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);

	scanf("%d%d%d", &N, &M, &S);

	int i, j, x, y;
		
	for(i = 1; i <= N; i++)
		DIST[i] = -1;

	struct nod * cnod, * nnod;

	for(i = 0; i < M; i++)
	{
		scanf("%d%d", &x, &y);
		if(noduri[x] != NULL)
		{
			cnod = noduri[x];

			while(cnod->next != NULL)
				cnod = cnod->next;

			nnod = malloc(sizeof(struct  nod));

			cnod->next = nnod;

			nnod->dest = y;
		}
		else
		{
			noduri[x] = malloc(sizeof(struct  nod));
			noduri[x]->dest = y;
		}
	
	}

	Q[1] = S;
	i = 1;
	j = 1;

	int D = 1;
	VIZ[S] = 1;
	DIST[S] = 0;

	while(j >= i)
	{
		cnod = noduri[Q[i]];
		
		while(cnod)
		{
			if(cnod->dest && !VIZ[cnod->dest])
			{
				VIZ[cnod->dest] = 1;
				DIST[cnod->dest] = DIST[Q[i]] + 1;
				j++;
				Q[j] = cnod->dest;
			}
	
			cnod = cnod->next ? cnod->next : NULL;
		};
		
		i++;
		D++;
	}

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

	return 0;
}