#include<cstdio>
#include<cstring>
#define infile "bfs.in"
#define outfile "bfs.out"
#define L 100005
using namespace std;

void citeste();
void rezolva();
void afiseaza();


typedef struct nod {
	int info;
	nod *urm;
} *pnod;
pnod v[L];

void add(pnod&,int);

int cost[L],c[L];

int n,m,s;

void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d %d",&n,&m,&s);
	
	int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		add(v[x],y);
	}
	
	fclose(stdin);
}


void add(pnod &dest, int val)
{
	pnod p;
	p = new nod;
	p->info=val;
	p->urm=dest;
	dest=p;
}


void rezolva()
{
	int prim,ultim;
	prim=ultim=1;
	
	memset(cost,-1,sizeof(cost));
	
	cost[s]=0;
	c[prim]=s;
	
	while(prim<=ultim)
	{
		pnod p;
		p=v[c[prim]];
		while(p)
		{
			if(cost[p->info]==-1)
			{
				cost[p->info]=cost[c[prim]]+1;
				c[++ultim]=p->info;
			}
		p=p->urm;
		}
		prim++;
	}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	for(int i=1;i<=n;i++)
		printf("%d\n",cost[i]);
	
	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}