<p>You are given a <strong>0-indexed</strong> 2D integer array <code>pairs</code> where <code>pairs[i] = [start<sub>i</sub>, end<sub>i</sub>]</code>. An arrangement of <code>pairs</code> is <strong>valid</strong> if for every index <code>i</code> where <code>1 &lt;= i &lt; pairs.length</code>, we have <code>end<sub>i-1</sub> == start<sub>i</sub></code>.</p>

<p>Return <em><strong>any</strong> valid arrangement of </em><code>pairs</code>.</p>

<p><strong>Note:</strong> The inputs will be generated such that there exists a valid arrangement of <code>pairs</code>.</p>

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

<pre>
<strong>Input:</strong> pairs = [[5,1],[4,5],[11,9],[9,4]]
<strong>Output:</strong> [[11,9],[9,4],[4,5],[5,1]]
<strong>Explanation:
</strong>This is a valid arrangement since end<sub>i-1</sub> always equals start<sub>i</sub>.
end<sub>0</sub> = 9 == 9 = start<sub>1</sub> 
end<sub>1</sub> = 4 == 4 = start<sub>2</sub>
end<sub>2</sub> = 5 == 5 = start<sub>3</sub>
</pre>

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

<pre>
<strong>Input:</strong> pairs = [[1,3],[3,2],[2,1]]
<strong>Output:</strong> [[1,3],[3,2],[2,1]]
<strong>Explanation:</strong>
This is a valid arrangement since end<sub>i-1</sub> always equals start<sub>i</sub>.
end<sub>0</sub> = 3 == 3 = start<sub>1</sub>
end<sub>1</sub> = 2 == 2 = start<sub>2</sub>
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.
</pre>

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

<pre>
<strong>Input:</strong> pairs = [[1,2],[1,3],[2,1]]
<strong>Output:</strong> [[1,2],[2,1],[1,3]]
<strong>Explanation:</strong>
This is a valid arrangement since end<sub>i-1</sub> always equals start<sub>i</sub>.
end<sub>0</sub> = 2 == 2 = start<sub>1</sub>
end<sub>1</sub> = 1 == 1 = start<sub>2</sub>
</pre>

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

<ul>
	<li><code>1 &lt;= pairs.length &lt;= 10<sup>5</sup></code></li>
	<li><code>pairs[i].length == 2</code></li>
	<li><code>0 &lt;= start<sub>i</sub>, end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>start<sub>i</sub> != end<sub>i</sub></code></li>
	<li>No two pairs are exactly the same.</li>
	<li>There <strong>exists</strong> a valid arrangement of <code>pairs</code>.</li>
</ul>

class Solution:

    # simple Dijkstra
    def dijkstra(self, graph, start):
        distances = {}
        heap = [(0, start)]

        while heap:
            dist, node = heappop(heap)
            if node in distances:
                continue
            distances[node] = dist
            for neighbor in graph[node]:
                if neighbor not in distances:
                    heappush(heap, (dist + 1, neighbor))

        return distances


    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        # Convert the pairs into and ajdacency list represented graph
        adj_list = defaultdict(list)
        reverse_adj_list = defaultdict(list)
        for s, e in pairs:
            adj_list[s].append(e)
            reverse_adj_list[e].append(s)

        # Determine start and end values by counting the incoming and outgoing
        # edges of each vertex.
        start = pairs[0][0]
        end = None
        end_count = defaultdict(int)
        for s, e in pairs:
            end_count[e] += 1
            if e == start:
                # if the graph has no explicit start, the route should
                # end at the randomly picked starting point
                end = s

        for k, l in adj_list.items():
            if len(l) > end_count[k]:
                # print(f"start change to {k} because it has appeared as start of {l}  which is more times than as end {end_count[k]}")
                start = k
                break
        
        for k, count in end_count.items():
            if len(adj_list[k]) < count:
                # print(f"end change to {k} because it has appeared as end {count} times which is more than the start of {adj_list[k]}")
                end = k
                break

        # dijkstra calculating the distance from end to all nodes
        distances = self.dijkstra(reverse_adj_list, end)


        # For each vertex, store the edges in an ascending order by distance to
        # the end node so that we can pop them off efficiently starting from largest
        for k in adj_list:
            adj_list[k].sort(key=lambda e: distances[e])

        # Now simply navigate the graph from the start node by always taking the
        # route that will take longer to the end
        r = []
        curr = start
        for i in range(len(pairs)):
            nxt = adj_list[curr].pop()

            r.append([curr, nxt])
            curr = nxt

        return r
90276