#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100004

using namespace std;
ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

vector <int> v[NMAX];
queue <int> c;
int sol[NMAX];
int n, m, s, i, x, y, vf, vf1;

int main()
{
 fin>>n>>m>>s;
 for (i=0; i<=n; i++)
     sol[i]=-1;
 sol[s]=0;
 for (i=1; i<=m; i++)
     {
      fin>>x>>y; v[x].push_back(y);
     }
 c.push(s);
 while (!c.empty())
       {
        vf=c.front();
        while (!v[vf].empty())
              {
               vf1=v[vf].back();
               if (sol[vf1]==-1 && vf1!=s)
                  {
                   c.push(vf1);
                   sol[vf1]=sol[vf]+1;
                  }
               v[vf].pop_back();
              }
        c.pop();
       }
 for (i=1; i<=n; i++)
     fout<<sol[i]<<' ';
 fout<<'\n';
 return 0;
}