#include<stdio.h>

#define MAX 102400

struct nod
{
	int val; 
	nod * adr;
}* start[MAX], * stop[MAX];

void add(int from, int to)
{
	nod *p;
	p = new nod;
	p->val = to;
	p->adr = NULL;
	if (!start[from])
		start[from] = p;
	else
		stop[from]->adr = p;
	stop[from] = p;
}

int cost[MAX], q[MAX];
int n, m, s;

void bfs()
{
	int i, level=1;
	nod *p;
	
	for (i=1; i<=n; i++)
		cost[i] = -1;
	cost[s] = 0;
	q[1]=s;
	
	for (i=1; i<=level; i++)
	{
		p = start[ q[i] ];
		while (p)
		{
			if (/*cost[ q[i] ] + 1  < cost [p->val] ||*/ cost[p->val] < 0 )
			{
				cost [p->val] = cost[ q[i] ]+ 1;
				level++;
				q[level] = p->val;
			}
			p = p->adr;
		}
	}
}

int main()
{	
	int i, a, b;
	
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &s);
	
	for (i=1; i<=m; i++)
	{
		scanf("%d %d", &a, &b);
		add(a,b);
	}
	bfs();
	for (i=1; i<=n; i++)
		printf("%d ", cost[i]);
	return 0;
}