#include<stdio.h>
#include<assert.h>

#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

const int knmax = 100005;
int verts, edges, source, vis[knmax], sol[knmax];
vector<int> graph[knmax];

void read(){
  assert(freopen("bfs.in", "r", stdin) != NULL);

  scanf("%d%d%d", &verts, &edges, &source);

  int i, aux_x, aux_y;
  for(i = 1; i <= edges; ++i){
    scanf("%d%d", &aux_x, &aux_y);

    graph[aux_x].push_back(aux_y);
  }

}

void init(){
  for(int i = 1; i <= verts; ++i){
    vis[i] = 0;
    sol[i] = -1;
  }

}

void solve(){
  init();
  vis[source] = 1;
  sol[source] = 0;

  int now = source;
  queue<int> q;
  q.push(now);
  vector<int>::iterator it;

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

    for(it = graph[now].begin(); it < graph[now].end(); ++it)
      if(!vis[*it]){
        vis[*it] = 1;
        sol[*it] = sol[now] + 1;
        q.push(*it);
      }
  }

}

void write(){
  assert(freopen("bfs.out", "w", stdout) != NULL);

  for(int i = 1; i <= verts; ++i)
      printf("%d ",sol[i]);

}

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