#include <fstream>
#include <queue>
using namespace std;

#define NMAX 100000

struct neighbor {
  int id;
  neighbor* next;
};

int N, M, S;
bool visited[NMAX+1];
int dist[NMAX+1];
neighbor* adj_list[NMAX+1];

void readInput();
void printOutput();
void BFS();

int main(void)
{
  readInput();
  BFS();
  printOutput();
  return 0;
}

void readInput()
{
  int from, to;
  ifstream f("bfs.in");

  f >> N >> M >> S;
  for (int i=0;i<M;i++)
  {
    f >> from >> to;
    neighbor* x = new neighbor;
    x->id = to-1;
    x->next = NULL;

    if (adj_list[from-1] != NULL)
    {
      x->next = adj_list[from-1];      
    }
    adj_list[from-1] = x;
  }

  f.close();
}

void printOutput()
{
  ofstream g("bfs.out");

  for (int i=0;i<N;i++)
  {
    g << dist[i] << " ";
  }
  g << "\n";

  g.close();
}

void BFS()
{
  queue<int> Q;

  for (int i=0;i<N;i++)
  {
    visited[i] = false;
    dist[i] = -1;
  }

  visited[S-1] = true;
  dist[S-1] = 0;
  Q.push(S-1);
  while (!Q.empty())
  {
    int x = Q.front();
    Q.pop();
    
    neighbor* it = adj_list[x];
    while (it != NULL)
    {
      if (!visited[it->id])
      {
        dist[it->id] = dist[x]+1;
        visited[it->id] = true;
        Q.push(it->id);
      }
      it = it->next;
    }
  }
}