#include <bits/stdc++.h>

#define N 100005 
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int n, m, s;
int dist[N];
vector<int> graf[N];

void read() {
  f>>n>>m>>s;
  int x, y;
  for(int i = 1;i <= m;++i) {
    f>>x>>y;
    graf[x].push_back(y);
  }
  f.close();
}

void solve() {
  for(int i = 1;i <= n;++i) {
    dist[i] = -1;
  }
  dist[s] = 0;

  queue<int> q;
  q.push(s);

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

    for(const auto& vecin : graf[top]) {
      if(dist[vecin] == -1) {
        dist[vecin] = dist[top] + 1;
        q.push(vecin);
      }
    }
  }
  for(int i = 1;i <= n;++i) {
    g<<dist[i]<<" ";
  }
  g.close();
}


int main() {
  read();
  solve();
  return 0;
}