#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int NMAX = 100001;
const int MMAX = 1000001;
struct muchie {
	int x,y;
};
int cost[NMAX],l[NMAX],c[NMAX],*v[NMAX],n;
muchie *a;
inline void bfs(int nod)
{
	int i,st,dr;
	for(i=1;i<=n;i++)
		cost[i]=-1;
	st=1;
	dr=1;
	c[st]=nod;
	cost[nod]=0;
	while(st<=dr) {
		for(i=0;i<=l[c[st]];i++) 
			if(cost[v[c[st]][i]]==-1) {
				cost[v[c[st]][i]]=cost[c[st]]+1;
				c[++dr]=v[c[st]][i];
			}
		st++;
	}
}
int main ()
{
	int m,i,s;
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%d %d %d",&n,&m,&s);
	a=new muchie[m+1];
	for(i=1;i<=m;i++) {
		scanf("%d %d",&a[i].x,&a[i].y);
		l[a[i].x]++;
	}
	fclose(stdin);
	for(i=1;i<=n;i++) {
		v[i]=new int[l[i]];
		l[i]=-1;
	}
	for(i=1;i<=m;i++) 
		v[a[i].x][++l[a[i].x]]=a[i].y;
	delete a;
	bfs(s);
	for(i=1;i<=n;i++)
		printf("%d ",cost[i]);
	fclose(stdout);
	return 0;
}