#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n,i,j,k,m,x,y,S,d[100005],c,g[100005],v[100005];
vector <int>A[100005];
queue<int> C;
int main()
{fin>>n>>m>>S;
 for(i=1;i<=m;i++)
    {fin>>x>>y;
     A[x].push_back(y);
     g[x]++;
    }
 for(i=1;i<=n;i++)
    d[i]=-1;
 C.push(S);
 d[S]=0;
 v[S]=1;
 while(C.size()>0)
      {c=C.back();
       C.pop();
       for(i=0;i<g[c];i++)
          {if(v[A[c][i]]==0)
             {C.push(A[c][i]);
              if(d[A[c][i]]==-1)d[A[c][i]]=d[c]+1;
                else d[A[c][i]]=min(d[c]+1,d[A[c][i]]);
             }
          }
      }
 for(i=1;i<=n;i++)
    fout<<d[i]<<" ";
}