from sage.combinat.cyclic_sieving_phenomenon import orbit_decomposition
def toggle_labelling(G, pi, i, j):
    if G.has_edge(pi.index(i), pi.index(j)):
        return pi
    sigma = [j if e == i else i if e == j else e for e in pi]
    return Permutation(sigma)

def toric_promotion_labelling(G, pi):
    n = G.num_verts()
    assert set(G.vertices()) == set(range(n))
    for i in range(1, n):
        pi = toggle_labelling(G, pi, i, i+1)
    return toggle_labelling(G, pi, n, 1)

def toric_promotion_labelling_orbits(G):
    G = G.canonical_label().copy(immutable=True)
    return toric_promotion_labelling_orbits_aux(G)

@cached_function
def toric_promotion_labelling_orbits_aux(G):
    n = G.num_verts()
    return orbit_decomposition(Permutations(n),
                               lambda pi: toric_promotion_labelling(G, pi))

def statistic(G):
    return len(toric_promotion_labelling_orbits(G))