Canonical Euler Trail

You are given a connected undirected multigraph with vertices numbered from 1 through n. Edge i joins edgeFrom[i] and edgeTo[i]. Parallel edges are allowed.
The graph is guaranteed to have an Euler trail: a vertex sequence that uses every edge exactly once. Return the trail produced by this canonical Hierholzer order:
If exactly two vertices have odd degree, start at the smaller one. Otherwise start at the smallest vertex incident to an edge.
Whenever the traversal is at a vertex, consume the unused incident edge whose other endpoint is smallest. If several such edges have the same endpoint, consume the one with the smallest input index.
Use Hierholzer backtracking and reverse the completed postorder sequence.

Function
canonicalEulerTrail(n: int, edgeFrom: int[], edgeTo: int[]) → int[]

Examples
Example 1
n = 3
edgeFrom = [1,2]
edgeTo = [2,3]
return = [1,2,3]
The only Euler trail starts at odd-degree vertex 1 and follows both edges.
Example 2
n = 3
edgeFrom = [1,2,3]
edgeTo = [2,3,1]
return = [1,2,3,1]
All degrees are even, so traversal starts at vertex 1 and takes neighbor 2 first.
Example 3
n = 4
edgeFrom = [1,1,2,3]
edgeTo = [2,3,4,4]
return = [1,2,4,3,1]
Vertices 1 and 4 are odd; start at 1 and consume the edge to 2 before the edge to 3.

Constraints
2 <= n <= 10^5.
1 <= edgeFrom.length == edgeTo.length <= 2 * 10^5.
Every endpoint is between 1 and n, and no edge is a self-loop.
The graph is connected after ignoring isolated vertices and has either zero or two odd-degree vertices.
Every vertex from 1 through n is incident to at least one edge.

The trick is Hierholzer with sorted adjacency. For each vertex, store (neighbor, edge index) pairs sorted ascending, and keep a pointer per vertex. Mark edges used by index so the parallel and reverse copies of an edge aren't taken twice. Start at the smaller odd vertex if there are two odd ones, else at vertex 1, since every vertex has an edge. Run DFS, take the next unused edge, recurse, and push the vertex to the postorder on return. Reverse at the end. The big pitfall is recursion depth: 2 * 10^5 edges will overflow the stack in many languages, so use an explicit stack. Second pitfall is forgetting to skip used edges when advancing the pointer. Sorting costs O(E log E), traversal is O(E). If you blank on the iterative version during the live OA, StealthCoder is the hedge that gets you a working one.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.