1
# Hierholzer Algorithm
2
from collections import defaultdict
3

4

5
class Solution:
6
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
7
        G = defaultdict(list)
8
        din = defaultdict(int)
9
        dout = defaultdict(int)
10
        for v, w in pairs:
11
            G[v].append(w)
12
            dout[v] += 1
13
            din[w] += 1
14
        start = pairs[0][0]
15
        for v in G:
16
            if din[v] + 1 == dout[v]:
17
                start = v
18
        route = []
19

20
        def dfs(v):
21
            while G[v]:
22
                w = G[v].pop()
23
                dfs(w)
24
            route.append(v)
25

26
        dfs(start)
27
        route.reverse()
28
        return [[route[i], route[i + 1]] for i in range(len(route) - 1)]