#include<stdio.h>
#include<malloc.h>
using namespace std;

typedef struct _nod
{
	long int info;
//	int cost;
	struct _nod *adr;
} nod;

typedef struct
{
	nod *cap;
} list;

list A[100001];
long int C[1000001];
long int viz[100001];
long int n;
long int m;
long int s;

void citire(void)
{
	long int a;
	long int b;
//	int c;
	FILE *f = fopen("bfs.in","r");
	
	fscanf(f,"%ld %ld %ld",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%ld %ld",&a,&b);
		nod *nou = (nod*)malloc(sizeof(nod));
		nou->info = b;
//		nou->cost = c;
		nou->adr = A[a].cap;
		A[a].cap = nou;
//		nod *nou1 = (nod*)malloc(sizeof(nod));
//		nou1->info = a;
//		nou1->cost = c;
//		nou1->adr = A[b].cap;
//		A[b].cap = nou1;
	}
	
	fclose(f);
}

void parcurgere(void)
{
	C[1] = s;
	long int nr = 0;
	viz[s] = 1;
	long int pi = 1;
	long int pf = 1;
	while(pi<=pf)
	{
		nr ++;
//		printf("%d ",C[pi]);
		pi ++;
		nod *q = A[C[pi-1]].cap;
		while(q)
		{
			if(!viz[q->info])
			{			
				C[++pf] = q->info;
				viz[C[pf]] = nr;
			}
			q = q->adr;
		}
	}
}

void afisare(void)
{
	FILE *f = fopen("bfs.out","w");
	
	viz[s] = 0;
	for(int i=1;i<=n;i++)
		if(viz[i] == 0 && i != s)
		  fprintf(f,"-1 ");
		else
		  fprintf(f,"%ld ",viz[i]);
		
	fclose(f);
}

int main()
{
	citire();
	parcurgere();
	afisare();
	return 0;
}