def color_graph(graph, colors):
    # Create a valid coloring for the graph
    # BFS
    to_visit = []
    to_visit.append(graph[0])

    while to_visit:
        node = to_visit.pop(0)
        if node.color != None:
       	    continue
        illegal_colors = []
        for neighbor in node.neighbors:
            if neighbor == node:
                raise Exception()
            if neighbor.color != None:
                illegal_colors.append(neighbor.color)
            else:
                to_visit.append(neighbor)
        for color in colors:
            if color not in illegal_colors:
                node.color = color
                print(node.label + " set to " + color)
                break


    return 0