import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.*;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("bfs.in"));
        PrintWriter out = new PrintWriter(new File("bfs.out"));

        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt() - 1;

        List<Node<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new Node<>(i));
        }

        for (int i = 0; i < m; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;

            if (u == v) continue;

            Node<Integer> nodeU = graph.get(u);
            Node<Integer> nodeV = graph.get(v);

            nodeU.neighbours.add(nodeV);
        }

        int[] costs = BFS(graph.get(s), n);

        if (costs.length > 0) {
            out.print(costs[0]);
        }

        for (int i = 1; i < costs.length; i++) {
            out.print(" " + costs[i]);
        }
        out.println();

        out.close();
        in.close();
    }

    private static int[] BFS(Node<Integer> s, int n) {
        Queue<Node<Integer>> queue = new LinkedList<>();

        int[] costs = new int[n];
        Arrays.fill(costs, -1);
        costs[s.value] = 0;

        queue.add(s);
        s.visited = true;

        while (!queue.isEmpty()) {
            Node<Integer> u = queue.poll();

            for (Node<Integer> v : u.neighbours) {
                if (!v.visited) {
                    costs[v.value] = costs[u.value] + 1;
                    v.visited = true;
                    queue.add(v);
                }
            }
        }

        return costs;
    }

    private static class Node<T> {

        private T value;
        private boolean visited;
        private List<Node<Integer>> neighbours;

        public Node(T value) {
            this.value = value;
            this.visited = false;
            this.neighbours = new ArrayList<>();
        }

    }

}