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

public class Main {

    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(new FileInputStream("bfs.in"));

        int N = in.nextInt();
        int M = in.nextInt();
        int S = in.nextInt();

        Graph graph = new Graph(N);

        for (int i = 0; i < M; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            graph.addEdge(x, y);
        }

        PrintWriter out = new PrintWriter(new FileOutputStream("bfs.out"));

        for (int d : BreadthFirstSearch.bfs(graph, S))
            out.print(d + " ");

        out.println();
        out.close();
    }

    static class Graph{
        private static class Edge{
            int node;
            int next;

            Edge(int node, int next){
                this.node = node;
                this.next = next;
            }
        }

        final static int NIL = -1;
        private int[] head;
        private ArrayList<Edge> graph;

        private int N;
        private int counter;

        Graph(int N){
            initialize(N);
        }

        public int getN() {
            return N;
        }

        private void initialize(final int N){
            head = new int[N];
            graph = new ArrayList<>();

            this.N = N;
            this.counter = 0;

            Arrays.fill(head, NIL);
        }

        void addEdge(int x, int y){
            assert 1 <= x && x <= N;
            x--; y--;
            graph.add(new Edge(y, head[x]));
            head[x] = counter++;
        }

        int getHead(int node){
            assert 1 <= node && node <= N;
            node--;
            return head[node];
        }

        int getNext(int p){
            assert 0 <= p && p < counter;
            return graph.get(p).next;
        }

        int getNeighbour(int p){
            assert 0 <= p && p < counter;
            return graph.get(p).node + 1;
        }
    }

    static class BreadthFirstSearch {
        static int[] bfs(Graph graph, int source){
            final int N = graph.getN();

            int[] distance = new int[N];
            Arrays.fill(distance, -1);
            Queue<Integer> queue = new LinkedList<>();

            source--;
            distance[source] = 0;
            queue.add(source);

            while (!queue.isEmpty()){
                int node = queue.remove();

                for (int p = graph.getHead(node + 1); p != Graph.NIL; p = graph.getNext(p)) {
                    int son = graph.getNeighbour(p) - 1;

                    if (distance[son] == -1){
                        distance[son] = distance[node] + 1;
                        queue.add(son);
                    }
                }
            }

            return distance;
        }
    }

    static class InputReader{
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 65536);
            tokenizer = null;
        }

        private String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()){
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
                catch (IOException e){
                    throw new RuntimeException(e);
                }
            }

            return  tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        String nextString(){
            return nextToken();
        }
    }
}