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 IOException {
        FileInputStream input = new FileInputStream("bfs.in");
        BufferedReader reader = new BufferedReader(new InputStreamReader(input));
        StringTokenizer st = new StringTokenizer(reader.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        adjList = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            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] + " ");
        }
        writer.close();
    }
}