#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,size;
    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=0; size=1;
    b[S]=0;
    while (p<size) {
          i=c[p];
          for (j=0; j<a[i].size (); j++) {
              k=a[i].at (j);
              if (b[k]==-1) {
                 b[k]=b[i]+1;
                 c[size]=k; size++;
              }
          }
          p++;
    }
    for (i=1; i<=N; i++) out<<b[i]<<" ";
    out<<"\n";
    in.close (); out.close ();
    return 0;
}