#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define Nn 100005
vector<int> lista[Nn];
int cost[Nn],ver[Nn],que[Nn],n;
void BFS(int Start)
{
	int it,i;
    memset(ver,0,sizeof(ver));
    memset(cost,0,sizeof(cost));
    memset(que,0,sizeof(que));
    int qs=1,nr=0,cont=0;
    que[0]=Start;
    for( it=0;it<qs;it++)
	{
		ver[que[it]]=1;
		if(it>=cont)
			{
				nr++;
				cont=qs;
			}
        for( i=0;i<lista[que[it]].size();i++)
        {
            if(!ver[lista[que[it]][i]])
            {
                ver[lista[que[it]][i]]=1;
                que[qs++]=lista[que[it]][i];
                cost[lista[que[it]][i]]=nr;
            }
        }
	}
	
	FILE *g=fopen("bfs.out","w");
	for(it=1;it<=n;it++)
		if(cost[it] || it==Start)
		    fprintf(g,"%d ",cost[it]);
		else
			fprintf(g,"-1 ");
}
int main ()
{
  int m,Start,a,b;

  FILE *f=fopen("bfs.in","r");

  fscanf(f,"%d %d %d",&n,&m,&Start);


  for(int i=0; i<m; i++)
  {
      fscanf(f,"%d %d",&a,&b);
      lista[a].push_back(b);
  }
  for(int i=0;i<m; i++)
	  for(int j=0;j<lista[i].size();j++)
		  printf("%d->%d\n",i,lista[i][j]);

    BFS(Start);
  return 0;
}