#include<stdio.h>
#include<string.h>
FILE *f=freopen("bfs.out","wt",stdout);
int a[100001][10001],n,s;
int cost[100001];
void BFS();
int main()
{int  i,m,x,y;
	freopen("bfs.in","rt",stdin);
	scanf("%d %d %d",&n,&m,&s);
	for(i=1;i<=m;++i) 
	  {scanf("%d %d",&x,&y);
	   a[x][++a[x][0]]=y;
	  }
	BFS();
	for(i=1;i<=n;++i) printf("%d ",cost[i]);
	return 0;
}
bool uz[100001];
void BFS()
{
 	int  prim,ultim,j,x;
	int  v[100001];
	v[1]=s; prim=ultim=1; uz[s]=1;  
	    memset(cost,-1,sizeof(cost));  cost[s]=0;
	    while(ultim>=prim)
		{
			x=v[prim++];
			for(j=1;j<=a[x][0];++j)
				if(!uz[a[x][j]])
				  {
					  uz[a[x][j]]++;
					  cost[a[x][j]]=cost[x]+1;
					  v[++ultim]=a[x][j];
				}
		}
}