package org.example;

import java.io.*;
import java.util.*;

public class Bfs {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(new File("bfs.in"));
        int n = Integer.parseInt(scanner.next());
        int[] found = new int[n+1];
        Arrays.fill(found, -1);
        int m = Integer.parseInt(scanner.next());
        int s = Integer.parseInt(scanner.next());
        found[s] = 0;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int from = Integer.parseInt(scanner.next());
            int to = Integer.parseInt(scanner.next());
            if (!graph.containsKey(from)) {
                graph.put(from, new ArrayList<>());
            }
            graph.get(from).add(to);
        }
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while (!q.isEmpty()) {
            int curr = q.poll();
            for (var next : graph.getOrDefault(curr, List.of())) {
                if (found[next] == -1) {
                    found[next] = found[curr] + 1;
                    q.add(next);
                }
            }
        }
        FileWriter fileWriter = new FileWriter("bfs.out");
        PrintWriter printWriter = new PrintWriter(fileWriter);
        for (int i = 1; i <= n; i++) {
            printWriter.print(found[i]);
            if (i != n) {
                printWriter.print(' ');
            }
        }
        printWriter.close();
    }
}