1
class Solution {
2
 public:
3
  std::vector<int> restoreArray(std::vector<std::vector<int>> &vals) {
4
    std::unordered_map<int, std::vector<int>> pairs;
5

6
    for (const std::vector<int> &val : vals) {
7
      pairs[val[0]].push_back(val[1]);
8
      pairs[val[1]].push_back(val[0]);
9
    }
10

11
    std::vector<int> result;
12
    int start = -1000000;
13

14
    for (const auto &entry : pairs) {
15
      if (entry.second.size() == 1) {
16
        start = entry.first;
17
        break;
18
      }
19
    }
20

21
    int left = -1000000;
22
    result.push_back(start);
23

24
    for (int i = 1; i < vals.size() + 1; ++i) {
25
      const std::vector<int> &val = pairs[start];
26
      int newval = (val[0] == left) ? val[1] : val[0];
27
      result.push_back(newval);
28
      left = start;
29
      start = newval;
30
    }
31

32
    return result;
33
  }
34
};