import java.io.*;
import java.util.*;

public class Main {

  private static final List<Integer> EMPTY_LIST = Collections.emptyList();

  public static class DirectedGraph {

    private List<Integer>[] adjList;

    public DirectedGraph(int N) {
      adjList = (List<Integer>[]) new List[N+1];
    }

    public int size() {
      return adjList.length;
    }

    public Collection<Integer> neighbors(int u) {
      if (adjList[u] == null) {
        return EMPTY_LIST;
      } else {
        return adjList[u];
      }
    }

    public void addEdge(int u, int v) {
      if (adjList[u] == null) {
        adjList[u] = new LinkedList<>();
      }
      adjList[u].add(v);
    }
  }

  public static class BFS {

    private DirectedGraph g;
    private int[] levels;

    public BFS(DirectedGraph g) {
      this.g = Objects.requireNonNull(g);
      levels = new int[g.size()];
      Arrays.fill(levels, -1);
    }

    public void visit(int source) {
      Queue<Integer> q = new LinkedList<>();

      levels[source] = 0;
      q.offer(source);

      while(!q.isEmpty()) {
        int u = q.poll();
        for (int v : g.neighbors(u)) {
          if (levels[v] == -1) {
            levels[v] = levels[u] + 1;
            q.offer(v);
          }
        }
      }
    }
  }

  public static void main(String[] args) throws IOException {
    try (BufferedReader reader = new BufferedReader(new FileReader("bfs.in"));
         PrintWriter out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("bfs.out")), true)) {
      StringTokenizer st = new StringTokenizer(reader.readLine());

      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      int source = Integer.parseInt(st.nextToken());

      DirectedGraph g = new DirectedGraph(N);

      for (int i = 0; i < M; i++) {
        st = new StringTokenizer(reader.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        g.addEdge(u, v);
      }

      BFS bfs = new BFS(g);

      bfs.visit(source);

      for (int i = 1; i < g.size(); i++) {
        out.print(bfs.levels[i]);
        out.print(" ");
      }
    }
  }
}