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 {

    class VertexEntry {
        VertexEntry(int vertex, int distanceFromSource) {
            this.vertex = vertex;
            this.distanceFromSource = distanceFromSource;
        }

        int vertex;
        int distanceFromSource;
    }

    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 (source == destination) {
            return;
        }
        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);

        Queue<VertexEntry> queue = new LinkedList<>();
        queue.add(new VertexEntry(source, 0));
        paths[source] = 0;

        while (!queue.isEmpty()) {
            VertexEntry currentVertexEntry = queue.poll();
            int currentVertex = currentVertexEntry.vertex;
            int distanceFromSource = currentVertexEntry.distanceFromSource;

            List<Integer> adjVertices = adjList[currentVertex];
            if (adjVertices != null) {
                for (Integer adjVertix : adjVertices) {
                    if (paths[adjVertix] == -1) {
                        queue.add(new VertexEntry(adjVertix, distanceFromSource+1));
                        paths[adjVertix] = distanceFromSource+1;
                    }
                }
            }
        }

        return paths;
    }

}