#include <iostream>
#include <fstream>

using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");

const int dim = 100005;
const int maxm = 1000005;

int n,m,start,q[dim],st = 0,dr = -1,vf[2*maxm],urm[2*maxm],lst[dim],nr;
int dist[dim];

void Adauga(int x,int y)
{
   vf[++nr] = y;
   urm[nr] = lst[x];
   lst[x] = nr;
}

void BFS()
{
   dist[start] = 0;
   q[++dr] = start;
   while (st <= dr)
   {
      int x = q[st++];
      for (int p=lst[x]; p!=0; p = urm[p])
      {
        int y = vf[p];
        if (dist[y] == -1)
        {
            dist[y] = dist[x] + 1;
            q[++dr] = y;
        }
      }
   }
}

int main()
{
    in >> n >> m >> start;
    for (int i=1; i<=n; i++) dist[i] = -1;
    for (int i=1,x,y; i<=m; i++)
    {
        in >> x >> y;
        Adauga(x,y);
    }
    BFS();
    for (int i=1; i<=n; i++)
    {
       out << dist[i] << " ";
    }
    return 0;
}