Vertices may repeat while edges cannot. Edges, including parallel copies, are the consumable state; dead-end finishing stitches cycles into one trail.

Imagine laying every edge as a one-use ticket. Walk tickets until stuck, then write vertices backward while unwinding. Earlier cycles splice naturally into the final order.

What the function promises: Return an Euler trail from start or None if not all directed edges are used. Mutates only an internal adjacency copy.

def euler_trail(graph, start):
    edges = [list(reversed(neighbors)) for neighbors in graph]
    stack, answer, total = [start], [], sum(map(len, edges))
    while stack:
        u = stack[-1]
        if edges[u]:
            stack.append(edges[u].pop())
        else:
            answer.append(stack.pop())
    answer.reverse()
    return answer if len(answer) == total + 1 else None

assert euler_trail([[1,2],[0],[]], 0) == [0,1,0,2]
assert euler_trail([[1],[0],[3],[]], 0) is None

Work and storage: O(V+E) time and O(V+E) copied storage.

When to recognize it: Edges, including parallel copies, are the consumable state; dead-end finishing stitches cycles into one trail.

Check before applying it: Degree conditions alone do not ensure all nonzero-degree vertices belong to one usable component.

Sort outgoing edges in reverse and pop the smallest available; validate the same existence and connectivity conditions.