"""Kiểm tra một lịch hai ca, sau đó tìm phương án ghép phòng."""
from collections import defaultdict


def trung_nhom(cac_canh, ca):
    return [(a, b) for a, b in cac_canh if ca[a] == ca[b]]


def ghep_phong(mien_phong):
    """Trả ánh xạ lớp -> phòng, hoặc None nếu không có ghép đầy đủ."""
    chu_phong = {}

    def gan(lop, da_xet):
        for phong in sorted(mien_phong[lop]):
            if phong in da_xet:
                continue
            da_xet.add(phong)
            truoc = chu_phong.get(phong)
            if truoc is None or gan(truoc, da_xet):
                chu_phong[phong] = lop
                return True
        return False

    for lop in sorted(mien_phong, key=lambda key: (len(mien_phong[key]), key)):
        if not gan(lop, set()):
            return None
    return {lop: phong for phong, lop in chu_phong.items()}


def kiem_lich(canh, ca, mien_phong):
    if trung_nhom(canh, ca):
        return None
    theo_ca = defaultdict(dict)
    for lop, tiet in ca.items():
        theo_ca[tiet][lop] = mien_phong[lop]
    result = {}
    for tiet, mien in sorted(theo_ca.items()):
        assignment = ghep_phong(mien)
        if assignment is None:
            return None
        result[tiet] = assignment
    return result


if __name__ == "__main__":
    canh = [("A", "C"), ("B", "C")]
    rooms = {"A": {"Lab"}, "B": {"Lab"}, "C": {"P101"}}
    schedule = {"A": 1, "B": 1, "C": 2}
    assert trung_nhom(canh, schedule) == []
    assert kiem_lich(canh, schedule, rooms) is None
    rooms["B"].add("Lab2")
    assert kiem_lich(canh, schedule, rooms) == {
        1: {"A": "Lab", "B": "Lab2"}, 2: {"C": "P101"}
    }
    assert ghep_phong({"A": {"R1","R2"}, "B": {"R1","R3"}, "C": {"R1","R3"}})
    print("Màu hợp lệ. Ghép phòng sau khi thêm Lab2:", kiem_lich(canh, schedule, rooms))