# very long time
def statistic(G):
    def good_colouring(colouring):
        for (a,b) in Subsets(G.vertices(), 2):
            found = False
            for p in G.all_paths(a,b):
                e0 = tuple(sorted([p[0], p[1]]))
    
                for block in colouring:
                    if e0 in block:
                        break
                if all(tuple(sorted([p[i], p[i+1]])) in block for i in range(1, len(p)-1)):
                    found = True
                    break
            if not found:
                return False
        return True

    max = G.num_edges() - G.num_verts() + min(G.degree()) + 1
    for c in range(max, 0, -1):
        E = G.edges(labels=False, sort=True)
        for colouring in SetPartitions(E, c):
            if good_colouring(colouring):
                return c