from itertools import combinations

def timetable(exams,enrollments,slots):
    conflicts={e:set() for e in exams}
    for courses in enrollments.values():
        for a,b in combinations(courses,2):
            conflicts[a].add(b); conflicts[b].add(a)
    order=sorted(exams,key=lambda e:-len(conflicts[e]))
    assigned={}
    def solve(i):
        if i==len(order): return True
        exam=order[i]
        for slot in slots:
            if all(assigned.get(other)!=slot for other in conflicts[exam]):
                assigned[exam]=slot
                if solve(i+1): return True
                del assigned[exam]
        return False
    if not solve(0): print('Insufficient slots'); return None
    assert all(assigned[a]!=assigned[b] for a in exams for b in conflicts[a])
    for e in exams: print(e,assigned[e])
    return assigned



exams = input("Enter at least 6 unique exam names, separated by spaces: ").split()
if len(exams) < 6 or len(set(exams)) != len(exams):
    raise ValueError("Enter at least 6 distinct exams.")
slots = input("Enter at least 4 unique time slots, separated by spaces: ").split()
if len(slots) < 4 or len(set(slots)) != len(slots):
    raise ValueError("Enter at least 4 distinct time slots.")
student_count = int(input("Number of student enrollment records: "))
if student_count < 1:
    raise ValueError("Provide at least one enrollment record.")
enrollments = {}
for i in range(student_count):
    courses = input(f"Exams taken by student {i + 1}, separated by spaces: ").split()
    if not courses or any(course not in exams for course in courses):
        raise ValueError("Every enrollment must contain only listed exam names.")
    enrollments[f"S{i + 1}"] = list(dict.fromkeys(courses))

schedule = timetable(exams, enrollments, slots)
print("Exams:", len(exams), "| Available slots:", len(slots))
print("Schedule found:", schedule is not None)
if schedule is not None:
    print("Verified: no conflicting exams share a slot.")
