#include <fstream>
#include <cstring>
#include <queue>
#include <stack>
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;
stack <int> lda[72013];
int n,i,m,s,a,b,D[72013],viz[72013];

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

int main()
{
  cin>>n>>m>>s;
  memset(viz,0,sizeof(viz));
  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(b);
                    }
 while (!Q.empty()){
                    while(!lda[Q.front()].empty()){
                                                   if (viz[lda[Q.front()].top()]==0) {
                                                                                      Q.push(lda[Q.front()].top());
                                                                                      viz[lda[Q.front()].top()]=1;
                                                                                     }
                                                   D[lda[Q.front()].top()]=min(D[Q.front()]+1,D[lda[Q.front()].top()]);
                                                   lda[Q.front()].pop();
                                                   }
                    Q.pop();
                    }   
for (i=1;i<=n;++i)
    if (D[i]==INF) cout<<"-1 ";
                 else cout<<D[i]<<" ";
return 0;
}