#include <fstream>
#include <vector>
using namespace std;

ifstream in; ofstream out;
vector <long> a[100001];
long b[100001],c[100000],N,M,S;

int main () {
    in.open ("bfs.in"); out.open ("bfs.out");
    in>>N>>M>>S;
    long i,j,k,*p,*q;
    for (i=1; i<=M; i++) {
        in>>j>>k;
        a[j].push_back (k);
    }
    for (i=1; i<=N; i++) b[i]=-1;
    c[0]=S; p=c; q=p+1;
    b[S]=0;
    while ((q-p)) {
          i=*p;
          for (j=0; j<a[i].size (); j++) {
              k=a[i].at (j);
              if (b[k]==-1) {
                 b[k]=b[i]+1;
                 *q=k; q++;
              }
          }
          p++;
    }
    for (i=1; i<=N; i++) out<<b[i]<<" ";
    out<<"\n";
    in.close (); out.close ();
    return 0;
}