// https://infoarena.ro/job_detail/2610263?action=view-source

#include <bits/stdc++.h>

#define FILE_I "bfs.in"
#define FILE_O "bfs.out"

#define NODE_NO_PATH 900000

class Task {
  int n, m, s;
  std::vector< std::vector< int>> adj;
  std::vector<int> distante;

 public:
  void solve() {
    read();
    fa();
    print();
  }

 private:
  void read() {
    std::ifstream fin(FILE_I);
    fin >> n >> m >> s;
    adj.resize(n + 1);
    distante.resize(n + 1, NODE_NO_PATH);
    
    int x, y;
    for (int i = 0; i < m; ++i) {
      fin >> x >> y;
      adj[x].push_back(y);
    }
    fin.close();
  }

  void fa() {
    std::queue<int> q;
    q.push(s);
    distante[s] = 0;

    while (!q.empty()) {
      int node = q.front();
      q.pop();

      for (auto &x : adj[node]) {
        if (distante[node] + 1 < distante[x]) {
          distante[x] = distante[node] + 1;
          q.push(x);
        }
      }
    }
  }


  void print() {
    std::ofstream fout (FILE_O);
    for (int i = 1; i <= n; ++i) {
      if (distante[i] == NODE_NO_PATH) {
        fout << -1 << " ";
      } else {
        fout << distante[i] << " ";
      }
    }
    fout.close();
  }
};

int main() {
  Task *t = new Task();
  t->solve();
  delete t;
  return 0;
}