1106. Eulerian Circuit Using Hierholzer's Algorithm

Given a directed graph with n nodes and edges, return an Eulerian circuit — a closed walk using every edge exactly once — as the sequence of nodes visited, starting from the smallest node with an outgoing edge and choosing the lexicographically smallest next node at each step. Return an empty list if no Eulerian circuit exists (or there are no edges). The input is JSON {n, edges}.

Input: JSON {n, edges} (directed).

Output: Array — the circuit's node sequence, or empty.

Examples

Input: {"n":3,"edges":[[0,1],[1,2],[2,0]]}
Output: [0,1,2,0]
Explanation: A directed triangle circuit.

Input: {"n":3,"edges":[[0,1],[1,2]]}
Output: []
Explanation: Degrees are unbalanced.

Input: {"n":2,"edges":[[0,1],[1,0]]}
Output: [0,1,0]
Explanation: Back-and-forth circuit.

Constraints

• 1<=n<=10^5
• directed

Asked by