#include<stdio.h>
#define infile "bfs.in"
#define outfile "bfs.out"
#define nmax (100*1000+1)
#define mmax (1000*1000+1)
int c[nmax]; //vector de cost (respectiv pozitie)
struct lista
	{
	int n,p; //nodul, respectiv pozitia anterioara a lu frasu (au acelasi tata:P) :))
	} l[mmax];
int p[nmax]; //p[i]-retine pozitia din lista a ultimului sau copil
int n,m; //numarul de noduri, respectiv muchii
int s; //nodul de la care trebuie sa aflam drumul cel mai scurt catre fiecare nod din graf

//arc de la x la y
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
	{
	int up=p[x]; //pozitia ultimului copil al nodului x
	l[m].p=up; l[m].n=y; //salvez pozitia respectiv nodul
	p[x]=m; //s-a modificat ultimul fiu...salvez pozitia
	}

void citire(struct lista l[mmax], int p[nmax], int c[nmax], int *n, int *m, int *s)
	{
	int i,x,y;
	scanf("%d %d %d\n",n,m,s);
	for(i=1;i<=*m;i++)
		{
		scanf("%d %d",&x,&y);
		add(l,p,i,x,y); //adaugam arcul x->y
		}
	for(i=1;i<=*n;i++) c[i]=-1; //niciun nod nu a fost vizitat, deci avem costul -1
	}

//parcurgem graful in latime (din nodul s) si facem vectorul de cost
void bfs(struct lista l[mmax], int p[nmax], int c[nmax], int s)
	{
	int ul;
	int co[nmax],st,dr; //coada :P
	c[s]=0; st=dr=1; co[st]=s; //initialiam coada si costul
	while(st<=dr) //cat timp avem elemente in coada
		{
		ul=p[co[st]];
		while(ul) //cat timp nodul c[st] are copii
			{
			if(c[l[ul].n]==-1) //daca nu a fost vizitat
				{
				c[l[ul].n]=c[co[st]]+1; //costul nodului tata + 1
				co[++dr]=l[ul].n; //adaugam nodul in coada
				}
			ul=l[ul].p; //fratele anterior
			}
		st++; //inaintam in coada
		}
	}

void afisare(int c[nmax], int n)
	{
	int i;
	for(i=1;i<=n;printf("%d ",c[i++]));
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(l,p,c,&n,&m,&s);
bfs(l,p,c,s); //parcurgem graful din nodul s, si facem vectorul de costuri
afisare(c,n); //afisem vectorul de cost minim

fclose(stdin);
fclose(stdout);
return 0;
}