import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {
        BufferedReader in = new BufferedReader(new FileReader("bfs.in"));
        String temp[] = in.readLine().split(" ");
        int N = Integer.parseInt(temp[0]);
        int M = Integer.parseInt(temp[1]);
        int S = Integer.parseInt(temp[2]);
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= M; i++) {
            g.add(i, new ArrayList<Integer>());
        }
        for (int i = 0; i < M; i++) {
            temp = in.readLine().split(" ");
            int x = Integer.parseInt(temp[0]);
            int y = Integer.parseInt(temp[1]);
            g.get(x).add(y);
        }
        dist = new int[M];
        for (int i = 0; i < M; i++) {
            dist[i] = -1;
        }
        bfs(S, g);
        PrintWriter out = new PrintWriter("bfs.out");  
        for (int i = 1; i <= N; i++) {
            out.print(dist[i] + " ");
        }
        in.close();
        out.close();
    }

    static int dist[];

    private static void bfs(int src, List<List<Integer>> g) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        pq.add(src);
        dist[src] = 0;
        while (!pq.isEmpty()) {
            int n = pq.poll();
            for (Integer i : g.get(n)) {
                if (dist[i] == -1) {
                    dist[i] = dist[n] + 1;
                    pq.add(i);
                }
            }
        }
    }

}