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

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader("bfs.in"));
        DirectedGraph graph = new DirectedGraph(scanner.nextInt());
        int numEdges = scanner.nextInt();
        int source = scanner.nextInt()-1;
        for (int i=0; i<numEdges; i++) {
            graph.addEdge(scanner.nextInt()-1, scanner.nextInt()-1);
        }
        scanner.close();

        PrintWriter printWriter = new PrintWriter("bfs.out");
        for (int distance : graph.shortestPathsFrom(source)) {
            printWriter.printf("%d ", distance);
        }
        printWriter.close();
    }
}

class DirectedGraph {

    private List<Integer>[] adjList;

    @SuppressWarnings("unchecked")
    public DirectedGraph(int numVertices) {
        if (numVertices < 1) {
            throw new IllegalArgumentException("number of vertices should be positive");
        }
        adjList = new List[numVertices];
    }

    public void addEdge(int source, int destination) {
        if (source < 0 || source >= adjList.length) {
            throw new IllegalArgumentException("invalid source vertex: " + source);
        }
        if (destination < 0 || destination >= adjList.length) {
            throw new IllegalArgumentException("invalid source vertex: " + destination);
        }
        if (adjList[source] == null) {
            adjList[source] = new LinkedList<>();
        }
        adjList[source].add(destination);
    }

    int[] shortestPathsFrom(int source) {
        if (source < 0 || source >= adjList.length) {
            throw new IllegalArgumentException("invalid source vertex: " + source);
        }

        int[] paths = new int[adjList.length];
        Arrays.fill(paths, -1);
        boolean[] visited = new boolean[adjList.length];

        int distance = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);
        paths[source] = distance;

        while (!queue.isEmpty()) {
            int currentVertex = queue.poll();
            if (!visited[currentVertex]) {
                distance++;
                visited[currentVertex] = true;
                for (Integer adjVertix : adjList[currentVertex]) {
                    queue.add(adjVertix);
                    paths[adjVertix] = distance;
                }
            }
        }

        return paths;
    }

}