#include<fstream>
#include<list>
#include<queue>
using namespace std;
typedef list<long> LI;
typedef queue<long> QU;
typedef LI::iterator IT;
LI L[100000];
long v[100000];
QU c;
long r,n,m;
void cit()
{ifstream fin("bfs.in");
  fin>>n>>m>>r;
  int i,x,y;
   for(i=1;i<=m;++i)
   {fin>>x>>y;
    L[x].push_back(y);
   }
 fin.close();
}
void bf()
{c.push(r);
 long k,i;
 IT it;
 for(i=1;i<=n;i++)
	 v[i]=-1;
 v[r]=0;
 while(!c.empty())
 {k=c.front();
   for(it=L[k].begin();it!=L[k].end();it++)
	if(v[*it]==-1) 
    {v[*it]=v[k]+1;
	  c.push(*it);
	 }
  c.pop();
 }  
}
void afis()
{IT it;
 int i;
 ofstream fout("bfs.out");
  for(i=1;i<=n;i++)
    fout<<v[i]<<" ";  
  fout.close();
}
int main()
{cit();
 bf();
 afis();
 return 0;
}