<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>


def build_graph(edges):
    g = {}
    for source, target in edges:
        if source not in g:
            g[source] = []
        if target not in g:
            g[target] = []
        g[source].append(target)
    return g


def get_in_out_degrees(graph):
    in_degrees = {node: 0 for node in graph}
    out_degrees = {node: 0 for node in graph}
    for node in graph:
        for adjacent in graph[node]:
            in_degrees[adjacent] += 1
            out_degrees[node] += 1
    return in_degrees, out_degrees


def get_source_node(graph, in_degrees, out_degrees):
    for node in graph:
        if out_degrees[node] == in_degrees[node] + 1:
            return node
    return list(graph.keys())[0]  # Any node can be the source


class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        graph = build_graph(pairs)
        in_degrees, out_degrees = get_in_out_degrees(graph)
        source = get_source_node(graph, in_degrees, out_degrees)
        path = []

        def dfs(node):
            while out_degrees[node] != 0:
                out_degrees[node] -= 1
                dfs(graph[node][out_degrees[node]])
            path.append(node)

        dfs(source)

        n = len(path)
        res = [[None, None] for _ in range(n-1)]
        res[0][0] = path[-1]
        res[-1][1] = path[0]
        for i in range(n-2, 0, -1):
            res[n-i-2][1] = path[i]
            res[n-i-1][0] = path[i]

        return res
2066