import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;

public class Main {
    int N;
    int M;
    int S;
    List<List<Integer>> adjList;
    int[] dist;

    public static void main(String[] args) throws Exception {
        Main driver = new Main();
        driver.readInput();
        driver.solve();
        driver.writeOutput();
    }

    private void solve() {
        dist = new int[N + 1];
        Arrays.fill(dist, -1);
        dist[S] = 0;
        Queue<Integer> bfsQueue = new LinkedList<>();
        bfsQueue.add(S);
        while (!bfsQueue.isEmpty()) {
            int current = bfsQueue.remove();
            for (int neigh : adjList.get(current)) {
                if (dist[neigh] == -1) {
                    bfsQueue.add(neigh);
                    dist[neigh] = dist[current] + 1;
                }
            }
        }
    }

    private void readInput() throws FileNotFoundException {
        File input = new File("bfs.in");
        Scanner sc = new Scanner(input);
        N = sc.nextInt();
        M = sc.nextInt();
        S = sc.nextInt();

        adjList = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 1; i <= M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjList.get(from).add(to);
        }
    }

    private void writeOutput() throws IOException {
        PrintWriter writer = new PrintWriter("bfs.out", StandardCharsets.UTF_8);
        for (int i = 1; i <= N; i++) {
            writer.print(dist[i]);
            if (i < N)
                writer.print(" ");
        }
        writer.close();
    }
}