Constraints

• 0 <= n <= 500
• 0 <= len(bad_pairs) <= n * (n - 1) / 2
• Each bad pair contains two distinct test indices in the range [0, n - 1]
• bad_pairs may be given in any endpoint order

Examples

Solution

def solution(n, bad_pairs):
    # Normalize the hidden bad pairs and build bit-mask adjacency for the oracle.
    bad_masks = [0] * n
    normalized_bad = set()
    for a, b in bad_pairs:
        if a == b:
            continue
        if a > b:
            a, b = b, a
        normalized_bad.add((a, b))

    for a, b in normalized_bad:
        bad_masks[a] |= 1 << b
        bad_masks[b] |= 1 << a

    calls = 0

    def run_test(vertices):
        """Return True iff vertices contains no hidden bad pair."""
        nonlocal calls
        calls += 1

        mask = 0
        for x in vertices:
            mask |= 1 << x

        for x in vertices:
            if bad_masks[x] & mask:
                return False
        return True

    discovered_masks = [0] * n
    found = []

    for v in range(n - 1, -1, -1):
        # Greedily color the already-processed suffix using discovered bad pairs.
        color_classes = []
        color_masks = []

        for u in range(v + 1, n):
            placed = False
            for idx, cmask in enumerate(color_masks):
                # u can join this color class if it has no discovered conflict inside it.
                if discovered_masks[u] & cmask == 0:
                    color_classes[idx].append(u)
                    color_masks[idx] |= 1 << u
                    placed = True
                    break

            if not placed:
                color_classes.append([u])
                color_masks.append(1 << u)

        def search_color_class(class_vertices):
            if not class_vertices:
                return

            query_vertices = [v] + class_vertices
            if run_test(query_vertices):
                return

            if len(class_vertices) == 1:
                u = class_vertices[0]
                found.append([v, u])
                discovered_masks[v] |= 1 << u
                discovered_masks[u] |= 1 << v
                return

            mid = len(class_vertices) // 2
            search_color_class(class_vertices[:mid])
            search_color_class(class_vertices[mid:])

        for color_class in color_classes:
            search_color_class(color_class)

    found.sort()
    return (found, calls)

Time complexity: O(n * min(n, k + 1) + k log n) oracle calls, where k is the number of bad pairs. The provided simulation also spends time constructing and checking oracle subsets.. Space complexity: O(n^2) bits for adjacency bit masks plus O(k) output space.

Hints

1. If a candidate set C is internally compatible, then runTest({v} union C) tells you whether v conflicts with at least one element of C.
2. Process tests from right to left so that when handling v, all bad pairs inside the suffix v + 1 ... n - 1 are already known and can be used to build compatible groups.