class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        #TC: O(n)
        #SC: O(n) n = len(adjacentPairs)
        #just need to find the starting point

        Dict = collections.defaultdict(list)
        res = []
        for pair in adjacentPairs:
            Dict[pair[0]].append(pair[1])
            Dict[pair[1]].append(pair[0])

        for key in Dict:
            if len(Dict[key]) == 1:
                start = key
                break

        while True:
            res.append(start)

            for ele in Dict[start]:
                if len(res) == 1:
                    end = ele
                else:
                    if ele != res[-2]:
                        end = ele

            del Dict[start]
            if len(Dict) == 0:
                break
            start = end

        return res