#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
typedef struct celula {
                       int nod;
                       celula* next;
                       }*lista;
const int INF=99999999;
queue <int> Q;
vector <int> lda[100013];
int n,i,m,s,a,b,D[100013],viz[100013];

void add(int nod,lista &p)
{
  lista r=new celula;
  r->nod=nod;
  r->next=p;
  p=r;
}  

int main()
{
  cin>>n>>m>>s;
  for (i=1;i<=n;++i) viz[i]=0;
  for (i=1;i<=n;++i) D[i]=INF;
  D[s]=0;
  viz[s]=1;
  Q.push(s);
  for (i=1;i<=m;++i){
                     cin>>a>>b;
                     lda[a].push_back(b);
                    }
 while (!Q.empty()){
                   for (i=0;i<lda[Q.front()].size();++i)
                                              {
                                               if (viz[lda[Q.front()][i]]==0) 
                                                   {
                                                   Q.push(lda[Q.front()][i]);
                                                   viz[lda[Q.front()][i]]=1;
                                                   }
                                                   D[lda[Q.front()][i]]=min(D[Q.front()]+1,D[lda[Q.front()][i]]);
                                                   }
                    Q.pop();
                    }   
for (i=1;i<=n;++i)
    if (D[i]==INF) cout<<"-1 ";
                 else cout<<D[i]<<" ";
return 0;
}