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

#define ALB 1
#define GRI 2
#define NEGRU 3

typedef struct NOD
{
	int val;
	struct NOD *urm;
} Nod;

void init(Nod *list, int n)
{
	int i;
	for (i = 1; i <= n; i++)
		list[i].urm = NULL;
}

void add(Nod *list, int x, int y)
{
	Nod *nod = (Nod *)malloc(sizeof(Nod));
	nod->val = y;
	nod->urm = NULL;

	Nod *tmp = &list[x];
	while (tmp->urm) tmp = tmp->urm;
	tmp->urm = nod;
}

void print(Nod *list, int n)
{
	int i;
	Nod *tmp;
	for (i = 1; i <= n; i++)
	{
		printf("%d:", i);
		tmp = &list[i];
		tmp = tmp->urm;
		while (tmp)
		{
			printf("%d ", tmp->val);
			tmp = tmp->urm;
		}
		printf("\n");
	}
}

void bfs(Nod *list, int n, int s, int *d)
{
	int i, x, v;
	int *c = (int *)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++)
	{
		c[i] = ALB;
		d[i] = -1;
	}
	int *q  = (int *)malloc(sizeof(int) * (n + 1));

	d[s] = 0;
	c[s] = GRI;
	int p = 0, u = 0;
	q[p] = s;

	Nod *tmp;
	while (p <= u)
	{
		x = q[p++];
		tmp = &list[x];
		tmp = tmp->urm;
		while (tmp)
		{
			v = tmp->val;
			if (c[v] == ALB)
			{
				d[v] = d[x] + 1;
				q[++u] = v;
				c[v] = GRI;
			}
			tmp = tmp->urm;
		}
		c[x] = NEGRU;
	}
}

int main()
{
	int n, m, s, i, x, y;
	FILE *f, *g;

	f = fopen("bfs.in", "r");
	g = fopen("bfs.out", "w");

	fscanf(f, "%d %d %d", &n, &m, &s);

	Nod *list = (Nod *)malloc(sizeof(Nod) * (n + 1));
	init(list, n);
	for (i = 0; i < m; i++)
	{
		fscanf(f, "%d %d", &x, &y);
		add(list, x, y);
	}

	int *d = (int *)malloc(sizeof(int) * (n + 1));	

	bfs(list, n, s, d);
	
	for (i = 1; i <= n; i++)
		fprintf(g, "%d ", d[i]);

	fclose(f);
	fclose(g);

	return 0;
}