#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 100000

int q[MAXN], drumuri[MAXN];

vector <int>arb[MAXN];

void BFS(int s){
  int p, u, cu, i, lenght;
  p = 0;
  u = 1;
  q[0] = s;
  drumuri[s] = 1;
  lenght = 2;
  while(p < u){
    cu = u;
    while(p < cu){
      for(i = 0; i < arb[q[p]].size(); i++){
        if(drumuri[arb[q[p]][i]] == 0){
          drumuri[arb[q[p]][i]] = lenght;
          q[u] = arb[q[p]][i];
          u++;
        }
      }
      p++;
    }
    lenght++;
  }
}

int main()
{
    FILE *fin, *fout;
    int n, m, s, i, a, b;
    fin = fopen("bfs.in", "r");
    fscanf(fin, "%d%d%d", &n, &m, &s);
    for(i = 0; i < m; i++){
      fscanf(fin, "%d%d", &a, &b);
      if(a != b){
        arb[a - 1].push_back(b - 1);
      }
    }
    fclose(fin);
    BFS(s - 1);
    fout = fopen("bfs.out", "w");
    for(i = 0; i < n; i++){
      fprintf(fout, "%d ", drumuri[i] - 1);
    }
    fclose(fout);
    return 0;
}