#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

const int Nmax = 100555;
int N, M, a, b, s;

vector<int> G[Nmax];
int d[Nmax];

int main() {
  fin >> N >> M >> s;
  --s;
  memset(d, -1, (N+1)*sizeof(int));
  while(M--) {
    fin >> a >> b;
    --a, --b;
    G[a].push_back(b);
  }
  queue<int> Q;
  d[s] = 0;
  Q.push(s);
  while(!Q.empty()) {
    int x = Q.front(); Q.pop();
    for(auto y: G[x]) {
      if (d[y] == -1) {
        d[y] = d[x]+1;
        Q.push(y);
      }
    }
  }
  for (int i = 0; i < N; ++i)
    fout << d[i] << (i ==  N-1 ? '\n' :  ' ');

  return 0;
}