#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n,m,i,j,s,x,y,cap;
int nr[100001];
vector<int> v[100001];
queue<int> q;
int main()
{
    f>>n>>m>>s;
    for(i=1;i<=n;i++)
        nr[i]=-1;
    for(i=1;i<=m;i++)
      {
         f>>x>>y;
         v[x].push_back(y);
      }
    q.push(s);
    nr[s]=0;
/*    for(i=1;i<=n;i++)
    {
      for(j=0;j<v[i].size();j++)
         g<<v[i][j]<<" ";
      g<<'\n';
    }
   g<<'\n'; */
    while(!q.empty())
      {
         cap=q.front();
     //    g<<v[cap][0]<<'\n'; //  g<<nr[1]<<'\n'<<'\n';
         for(i=0;i<v[cap].size();++i)
            if(nr[v[cap][i]]==-1)
              {
                 q.push(v[cap][i]);// g<<v[cap][i]<<'\n';
                 nr[v[cap][i]]=nr[cap]+1;
              }
         q.pop();
      }
    for(i=1;i<=n;++i)
       g<<nr[i]<<" ";
    f.close();g.close();
    return 0;
}