#include <stdio.h>
#define INPUT "bfs.in"
#define OUTPUT "bfs.out"

struct nod
{
	int vec;
	nod *leg;
};

int main()
{
	int n, m, s;
	
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d %d %d", &n, &m, &s); --s;
	
	nod **graf = new nod*[n];
	int i;
	for(i = 0; i < n; ++i) graf[i] = NULL;
	
	int x, y;
	for(i = 0; i < m; ++i)
	{
		scanf("%d %d", &x, &y); 
		--x; --y;
		nod *temp = new nod;
		temp -> vec = y;
		temp -> leg = graf[x];
		graf[x] = temp;
		
	}
	
	int *queue = new int[n];
	int *dist = new int[n];
	for(i = 0; i < n; ++i)
		dist[i] = -1;
	
	int in , sf;
	queue[in=sf=0] = s;
	dist[s] = 0;
	for(; in <= sf; ++in)
	{
		int src = queue[in];
		nod *p;
		for(p = graf[src]; p; p = p -> leg)
			if(dist[p -> vec] < 0)
			{
				queue[++sf] = p -> vec;
				dist[p -> vec] = dist[src] + 1;
			}
	}
	
	for(i = 0; i < n - 1; ++i)
		printf("%d ", dist[i]);
	printf("%d\n", dist[n-1]);
	return 0;
}