import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class CampusBfs {
    static List<String> shortestPath(Map<String, List<String>> graph,
                                     String start, String target) {
        if (!graph.containsKey(start) || !graph.containsKey(target)) {
            return List.of();
        }
        Queue<String> queue = new ArrayDeque<>();
        Map<String, String> parent = new HashMap<>();
        parent.put(start, null);
        queue.add(start);

        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (current.equals(target)) break;
            for (String next : graph.getOrDefault(current, List.of())) {
                if (parent.containsKey(next)) continue;
                parent.put(next, current);
                queue.add(next);
            }
        }

        if (!parent.containsKey(target)) return List.of();
        List<String> path = new ArrayList<>();
        for (String node = target; node != null; node = parent.get(node)) {
            path.add(node);
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Map<String, List<String>> campus = Map.of(
            "Cổng", List.of("Hành lang", "Sân"),
            "Hành lang", List.of("Cổng", "Phòng lab"),
            "Sân", List.of("Cổng", "Thư viện"),
            "Phòng lab", List.of("Hành lang", "Thư viện"),
            "Thư viện", List.of("Sân", "Phòng lab"),
            "Nhà kho", List.of()
        );

        List<String> path = shortestPath(campus, "Cổng", "Phòng lab");
        if (!path.equals(List.of("Cổng", "Hành lang", "Phòng lab"))) {
            throw new AssertionError(path);
        }
        if (!shortestPath(campus, "Cổng", "Nhà kho").isEmpty()) {
            throw new AssertionError("Nhà kho phải tách biệt");
        }
        if (!shortestPath(campus, "Cổng", "Cổng").equals(List.of("Cổng"))) {
            throw new AssertionError("Điểm đầu trùng điểm cuối");
        }
        System.out.println(String.join(" -> ", path));
    }
}