# extremely stupid code
def is_proper_coloring(G, c):
    """
    assume that G has vertices {0,...,n-1}.
    """
    return not any(c[v] in [c[u] for u in G[v]] for v in G)

def villainy_coloring(G, c):
    """
    assume that G has vertices {0,...,n-1}.
    """
    villainy = None
    for c_pi in Permutations(c):
        if is_proper_coloring(G, c_pi):
            d = sum(1 for c1, c2 in zip(c, c_pi) if c1 != c2)
            if villainy is None or d < villainy:
                villainy = d
                if villainy == 0:
                    return villainy
    return villainy

def statistic(G):
    G = G.relabel(inplace=False)
    n = G.num_verts()
    chi = G.chromatic_number()
    villainy = 0
    for c in sage.graphs.graph_coloring.all_graph_colorings(G, chi, vertex_color_dict=True):
        c = [c[i] for i in range(n)]
        for c_pi in Permutations(c):
            d = villainy_coloring(G, c_pi)
            villainy = max(villainy, d)
    return villainy