import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        MyScanner in = new MyScanner("bfs.in");
        PrintWriter out = new PrintWriter("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<>();
        }
 
    }
 
    private static class MyScanner {
 
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;
 
        MyScanner(String filename) throws FileNotFoundException {
            bufferedReader = new BufferedReader(new FileReader(filename));
        }
 
        private String next() throws IOException {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            }
 
            return stringTokenizer.nextToken();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        void close() throws IOException {
            bufferedReader.close();
        }
    }
}