def mex(voisins, couleur):
    """la plus petite couleur non utilisée par les voisins"""
    n = len(voisins)
    dispo = [True] * (n + 1)
    for v in voisins:
        if v in couleur and couleur[v] <= n:
            dispo[couleur[v]] = False
    for c in range(n + 1):
        if dispo[c]:
            return c
    assert False # on n'arrivera jamais ici

def coloriage(g):
    """colorie graphe g avec un algorithme glouton"""
    couleur = {}
    n = 0
    for s in g.sommets():
        c = mex(g.voisins(s), couleur)
        couleur[s] = c
        n = max(n, c + 1)
    return couleur, n