import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.nio.file.Paths;
import java.io.FileWriter;
import java.io.IOException;

public class cod {

    static ArrayList<ArrayList<Integer>> neighborList;
    static int numarNoduri, targetNode;
    static ArrayList<Integer> distances;

    static void ReadData() {
        try (Scanner scanner = new Scanner(Paths.get("bfs.in"))) {
            if (!scanner.hasNextInt()) {
                throw new IllegalArgumentException("Fisierul trebuie sa contina un numar de noduri.");
            }
            numarNoduri = scanner.nextInt();
            int numarMuchii = scanner.nextInt();
            targetNode = scanner.nextInt();

            // Validations
            if (numarMuchii <= 0) {
                throw new IllegalArgumentException("Numarul de muchii trebuie sa fie pozitiv.");
            }
            if (numarNoduri <= 0) {
                throw new IllegalArgumentException("Numarul de noduri trebuie sa fie pozitiv");
            }
            if (targetNode <= 0 || targetNode > numarNoduri) {
                throw new IllegalArgumentException("Nod target iesit din range");
            }

            // read edges and build the graph
            neighborList = new ArrayList<ArrayList<Integer>>(numarNoduri + 1);
            for (int i = 0; i <= numarNoduri; i++) {
                neighborList.add(new ArrayList<Integer>());
            }
            while (numarMuchii-- > 0) {
                int nod1 = scanner.nextInt();
                if (nod1 <= 0 || nod1 > numarNoduri) {
                    throw new IllegalArgumentException("Nod 1 iesit din range");
                }
                int nod2 = scanner.nextInt();
                if (nod2 <= 0 || nod2 > numarNoduri) {
                    throw new IllegalArgumentException("Nod 2 iesit din range");
                }
                neighborList.get(nod1).add(nod2);
            }
        } catch (IOException e) {
            throw new RuntimeException("Nu pot deschide fisierul bfs.in", e);
        }
    }


    static void BFS() {
        distances = new ArrayList<Integer>(Collections.nCopies(numarNoduri, -1));
        Queue<Integer> nodQueue = new LinkedList<>();
        nodQueue.add(targetNode);
        distances.set(targetNode - 1, 0);
        while (!nodQueue.isEmpty()) {
            int actualNode = nodQueue.remove();
            for (int neighbor : neighborList.get(actualNode)) {
                if (distances.get(neighbor - 1) == -1) {
                    distances.set(neighbor - 1, distances.get(actualNode - 1) + 1);
                    nodQueue.add(neighbor);
                }
            }
        }
    }


    static void WriteData() {
        try {
            FileWriter writer = new FileWriter("bfs.out");
            for (int distance : distances) {
                writer.write(distance + " ");
            }
            writer.close();
        } catch (IOException e) {
            throw new RuntimeException("Nu se poate scrie in fisierul bfs.out", e);
        }
    }

    public static void main(String[] args) {
        ReadData();
        BFS();
        WriteData();
    }
}