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

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 List<Integer> getRelated(Integer currNode) {
            return adjList.get(currNode);
        }

        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();
                List<Integer> relatedNodes = g.getRelated(currNode);
                if (relatedNodes != null) {
                    int currDist = dist[currNode] + 1;
                    relatedNodes.forEach(node -> {
                        if (dist[node] == -1) {
                            dist[node] = currDist;
                            queue.add(node);
                        }
                    });
                }
            }
            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();
    }
}