def rewrite_arcs (label_map, nfa):
    """Rewrite the label arcs in a NFA according to the input remapping."""
    states = [[(label_map[label], tostate) for (label, tostate) in arcs]
              for arcs in nfa[2]]
    return (nfa[0], nfa[1], states, nfa[3], nfa[4])