1
class Solution {
2
  public int[][] validArrangement(int[][] pairs) {
3
    int n = pairs.length;
4

5
    int[][] ans = new int[n][2];
6
    for (int[] a : ans) {
7
      a[0] = -1;
8
      a[1] = -1;
9
    }
10

11
    Map<Integer, Integer> outdegree = new HashMap<>();
12
    Map<Integer, Deque<Integer>> out = new HashMap<>();
13

14
    for (int[] pair : pairs) {
15
      outdegree.put(pair[0], outdegree.getOrDefault(pair[0], 0) + 1);
16
      outdegree.put(pair[1], outdegree.getOrDefault(pair[1], 0) - 1);
17

18
      out.computeIfAbsent(pair[0], k -> new ArrayDeque<>());
19
      out.computeIfAbsent(pair[1], k -> new ArrayDeque<>());
20

21
      out.get(pair[0]).addLast(pair[1]);
22
    }
23

24
    for (Map.Entry<Integer, Integer> entry : outdegree.entrySet()) {
25
      if (entry.getValue() == 1) ans[0][0] = entry.getKey();
26
      if (entry.getValue() == -1) ans[n - 1][1] = entry.getKey();
27
    }
28

29
    if (ans[0][0] == -1) {
30
      ans[0][0] = pairs[0][0];
31
      ans[n - 1][1] = pairs[0][0];
32
    }
33

34
    int i = 0;
35
    int j = n - 1;
36
    while (i < j) {
37
      int from = ans[i][0];
38

39
      Deque<Integer> toList = out.get(from);
40

41
      if (toList.size() == 0) {
42
        ans[j][0] = ans[--i][0];
43
        ans[--j][1] = ans[j + 1][0];
44
      } else {
45
        ans[i++][1] = toList.removeLast();
46
        ans[i][0] = ans[i - 1][1];
47
      }
48
    }
49

50
    return ans;
51
  }
52
}