import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.util.function.Function;

public class Main {

    static class DirectedGraph {
        private final int nodesCount;
        private final List<List<Integer>> adjList = new ArrayList<>();

        public DirectedGraph(int n) {
            this.nodesCount = n;
            for (int i = 0; i <= n; ++i) {
                adjList.add(new ArrayList<>());
            }
        }

        public void link(int a, int b) {
            adjList.get(a).add(b);
        }

        public void applyOnRelated(Integer currNode, Function<Integer, Void> f) {
            List<Integer> relatedNodes = adjList.get(currNode);
            if (relatedNodes == null) {
                return;
            }
            relatedNodes.forEach(f::apply);
        }

        public int getNodesCount() {
            return nodesCount;
        }
    }

    static class Solver {

        public static int[] solve(DirectedGraph g, int source) {
            int[] dist = new int[g.getNodesCount() + 1];
            Arrays.fill(dist, -1);
            dist[source] = 0;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(source);
            while (!queue.isEmpty()) {
                Integer currNode = queue.poll();
                g.applyOnRelated(currNode, it -> {
                    int currDist = dist[currNode] + 1;
                    if (dist[it] == -1) {
                        dist[it] = currDist;
                        queue.add(it);
                    }
                    return null;
                });
            }
            return dist;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new FileReader("bfs.in"));
        PrintWriter pw = new PrintWriter("bfs.out");
        int n = sc.nextInt();
        int m = sc.nextInt();
        int source = sc.nextInt();
        DirectedGraph g = new DirectedGraph(n);
        while (m-- > 0) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            g.link(from, to);
        }
        sc.close();
        int[] d = Solver.solve(g, source);
        for (int i = 1; i < d.length; ++i) {
            pw.print(d[i] + " ");
        }
        pw.close();
    }
}