<p>There is an integer array <code>nums</code> that consists of <code>n</code> <strong>unique </strong>elements, but you have forgotten it. However, you do remember every pair of adjacent elements in <code>nums</code>.</p>

<p>You are given a 2D integer array <code>adjacentPairs</code> of size <code>n - 1</code> where each <code>adjacentPairs[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that the elements <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> are adjacent in <code>nums</code>.</p>

<p>It is guaranteed that every adjacent pair of elements <code>nums[i]</code> and <code>nums[i+1]</code> will exist in <code>adjacentPairs</code>, either as <code>[nums[i], nums[i+1]]</code> or <code>[nums[i+1], nums[i]]</code>. The pairs can appear <strong>in any order</strong>.</p>

<p>Return <em>the original array </em><code>nums</code><em>. If there are multiple solutions, return <strong>any of them</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> adjacentPairs = [[2,1],[3,4],[3,2]]
<strong>Output:</strong> [1,2,3,4]
<strong>Explanation:</strong> This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> adjacentPairs = [[4,-2],[1,4],[-3,1]]
<strong>Output:</strong> [-2,4,1,-3]
<strong>Explanation:</strong> There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> adjacentPairs = [[100000,-100000]]
<strong>Output:</strong> [100000,-100000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>adjacentPairs.length == n - 1</code></li>
	<li><code>adjacentPairs[i].length == 2</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= nums[i], u<sub>i</sub>, v<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li>There exists some <code>nums</code> that has <code>adjacentPairs</code> as its pairs.</li>
</ul>

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {



        // Some difficulties. Even though tracking odd and evens tells us the odd elements are
        // surely the ones on the corners, still need to preserve relative ordering of list construction
        // efficiently 



        // Track the connections as well? Can be seen as like given an edgeList and construct nodes IN ORDER


        // Maybe an adj matrix would help. Thus if we use an edge say (4,11) and 11 after 4, we can also set
        // that 4,11 edge is done now and also the 11,4 edge is done.


        // the problem is with the values of the nodes differ wildly and does not follow a 1...n pattern











        // oh they're UNIQUE. so either have frequency ONE or TWO in adjacentPairs



        // If they're unique, each element only has ONE neighbor if IT HAS FREQUENCY ONE
        // and TWO NEIGHBORS if they have FREQUENCY 2


        // Thus we can start with a freq one element

        // then go to its neighbor


        // then go to that element's right neighbor

        // and so on?




        // We can keep a map of edges. vertex to vertex
        // each edge in adjList is undirected so we can insert both sides u,v v,u
        // so we can lookup continuously to build our list


        // problem, 2 adjacent and ordering, but a list is unique

        // for edxample 2->3->7->9
        // we insert 3,2 3,7 2,3 7,3
        // so need multimap?



        // how about an unordered map of int to vector to represent connections for each element
        unordered_map<int, vector<int>> connections;



        for(auto & pair : adjacentPairs) {
            if(connections.count(pair[0]) == 0) {
                connections.insert(make_pair(pair[0], vector<int>(1, pair[1])));
            } else {
                connections[pair[0]].push_back(pair[1]);
            }

            if(connections.count(pair[1]) == 0) {
                connections.insert(make_pair(pair[1], vector<int>(1, pair[0])));
            } else {
                connections[pair[1]].push_back(pair[0]);
            }
        }




        // Find one that has a vector list of size 1. There should be two for both ends of the list, but either
        // will do to start
        vector<int> originalList;

        for(auto x : connections) {
            //cout << "x val " << x.first << " has " << x.second.size() << " connections " << "\n";
            if(x.second.size() == 1) {
                originalList.push_back(x.first);
                //cout << "Push back " << x.first << "\n";
                int currElem = x.first;
                int nextElem = x.second[0];


                // Continue to build the list
                while(originalList.size() < adjacentPairs.size() + 1) {
                    // Push the next element
                    originalList.push_back(nextElem);
                    //cout << "Push back " << nextElem << "\n";

                    if(connections[nextElem].size() == 2) {
                        // We don't want to go back to currElem
                        if(connections[nextElem][0] == currElem) {
                            currElem = nextElem;
                            nextElem = connections[nextElem][1];
                        } else {
                            currElem = nextElem;
                            nextElem = connections[nextElem][0];
                        }
                    } else {
                        // If size is 1, then it is the final boundary
                    }

            

                }




                break;
            }
        }








        return originalList;




    }
};
88803