Given a directed multigraph that has an Eulerian trail starting at start, return the lexicographically smallest such trail as the list of nodes it visits, which has len(edges) + 1 entries. Return [] when no Eulerian trail from start exists.
The greedy rule — always leave by the smallest-numbered unused edge — can strand you at a dead end with edges still unused. Hierholzer's answer is to keep going anyway and record a node only once it has no unused edges left, building the trail backwards.
Write smallest_trail(n, edges, start).
Examples
Input: n = 3, edges = [(0, 1), (1, 2), (2, 0)], start = 0
Output: [0, 1, 2, 0]
Input: n = 4, edges = [(0, 1), (1, 0), (0, 2), (2, 3), (3, 0)], start = 0
Output: [0, 1, 0, 2, 3, 0]
Constraints
1 <= n <= 10**4,0 <= len(edges) <= 10**5- If the graph has an Eulerian path rather than a cycle, it must begin at
start, or the answer is[].
Goals
- Build an actual Eulerian trail rather than deciding that one exists
- Take the smallest available next node and still never get stuck
- Collect the trail as the recursion unwinds, not as it descends