You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 &lt;= i &lt; pairs.length, we have endi-1 == starti.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

&nbsp;
Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 9 == 9 = start1 
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3


Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.


Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2


&nbsp;
Constraints:


	1 &lt;= pairs.length &lt;= 105
	pairs[i].length == 2
	0 &lt;= starti, endi &lt;= 109
	starti != endi
	No two pairs are exactly the same.
	There exists a valid arrangement of pairs.


#Hierholzer Algorithm
from collections import defaultdict
class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        G = defaultdict(list)
        din = defaultdict(int)
        dout = defaultdict(int)
        for v, w in pairs:
            G[v].append(w)
            dout[v] += 1
            din[w] += 1
        start = pairs[0][0]
        for v in G:
            if din[v]+1 == dout[v]:
                start = v
        route = []
        def dfs(v):
            while G[v]:
                w = G[v].pop()
                dfs(w)
            route.append(v)
        dfs(start)
        route.reverse()
        return [[route[i],route[i+1]] for i in range(len(route)-1)]
class Solution {
    public int[][] validArrangement(int[][] pairs) {
        int n = pairs.length;
        
        int[][] ans = new int[n][2];
        for (int[] a : ans) {
            a[0] = -1;
            a[1] = -1;
        }
        
        Map<Integer, Integer> outdegree = new HashMap<>();
        Map<Integer, Deque<Integer>> out = new HashMap<>();
        
        for (int[] pair : pairs) {
            outdegree.put(pair[0], outdegree.getOrDefault(pair[0], 0) + 1);
            outdegree.put(pair[1], outdegree.getOrDefault(pair[1], 0) - 1);
            
            out.computeIfAbsent(pair[0], k -> new ArrayDeque<>());
            out.computeIfAbsent(pair[1], k -> new ArrayDeque<>());
            
            out.get(pair[0]).addLast(pair[1]);
        }
        
        for (Map.Entry<Integer, Integer> entry : outdegree.entrySet()) {
            if (entry.getValue() == 1) ans[0][0] = entry.getKey();
            if (entry.getValue() == -1) ans[n - 1][1] = entry.getKey();
        }
        
        if (ans[0][0] == -1) {
            ans[0][0] = pairs[0][0];
            ans[n - 1][1] = pairs[0][0];
        }
        
        int i = 0;
        int j = n - 1;
        while (i < j) {
            int from = ans[i][0];
            
            Deque<Integer> toList = out.get(from);
            
            if (toList.size() == 0) {
                ans[j][0] = ans[--i][0];
                ans[--j][1] = ans[j + 1][0];
            } else {
                ans[i++][1] = toList.removeLast();
                ans[i][0] = ans[i - 1][1];
            }
        }
        
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        int m = pairs.size();
        // Eulerian Path
        unordered_map<int, stack<int>> adj;
        unordered_map<int, int> in;
        unordered_map<int, int> out;
        // reserve spaces for unordered_map may help in runtime.
        adj.reserve(m);
        in.reserve(m);
        out.reserve(m);
        for (int i = 0; i < m; i++) {
            int u = pairs[i][0], v = pairs[i][1];
            in[v]++;
            out[u]++;
            adj[u].push(v);
        }
        // find the starting node
        int start = -1;
        for (auto& p : adj) {
            int i = p.first;
            if (out[i] - in[i] == 1) start = i;
        }
        if (start == -1) {
            // Eulerian Circuit -> start at any node
            start = adj.begin()->first;
        }
        vector<vector<int>> ans;
        euler(adj, ans, start);
        reverse(ans.begin(), ans.end());
        return ans;
    }
private:
    void euler(unordered_map<int, stack<int>>& adj, vector<vector<int>>& ans, int curr) {
        auto& stk = adj[curr];
        while (!stk.empty()) {
            int nei = stk.top();
            stk.pop();
            euler(adj, ans, nei);
            // postorder
            ans.push_back({curr, nei});
        }
    }
};
var validArrangement = function(pairs) {
  let graph = {};
  let degrees = {}; // outdegree: positive, indegree: negative
  for (var [x, y] of pairs) {
    if (!graph[x]) graph[x] = [];
    graph[x].push(y);
    if (degrees[x] === undefined) degrees[x] = 0;
    if (degrees[y] === undefined) degrees[y] = 0;
    degrees[x]++;
    degrees[y]--;
  }
  let start = pairs[0][0];
  for (var [x] of pairs) {
    if (degrees[x] === 1) start = x; // one extra outdegree
  }
  let ans = [];
  dfs(start);

  function dfs(node) {
    while ((graph[node] || []).length) {
      let neighbor = graph[node].pop();
      dfs(neighbor);
      ans.push([node, neighbor]);
    }
  }
  return ans.reverse();
};
Valid Arrangement of Pairs