class Solution {
    private data class Graph(
        val neighbors: Map<Int, ArrayDeque<Int>>,
        val ingoing: Map<Int, Int>,
        val outgoing: Map<Int, Int>,
    )

    private fun constructGraph(pairs: Array<IntArray>): Graph {
        val neighbors = mutableMapOf<Int, ArrayDeque<Int>>()
        val ingoing = mutableMapOf<Int, Int>()
        val outgoing = mutableMapOf<Int, Int>()

        pairs.forEach { pair ->
            val (left, right) = pair[0] to pair[1]

            neighbors.getOrPut(left) { ArrayDeque<Int>() }.add(right)
            outgoing[left] = 1 + outgoing.getOrDefault(left, 0)
            ingoing[right] = 1 + ingoing.getOrDefault(right, 0)
        }

        return Graph(neighbors, ingoing, outgoing)
    }

    private fun findStart(g: Graph): Int =
        g.outgoing.keys.firstOrNull {
            g.outgoing[it] == 1 + g.ingoing.getOrDefault(it, 0)
        } ?: g.outgoing.keys.first()

    private fun visit(
        g: Graph,
        path: MutableList<Int>,
        u: Int,
    ) {
        val neighbors = g.neighbors.getOrDefault(u, null)
        while (neighbors != null && neighbors.isNotEmpty()) {
            val v = neighbors.removeFirst()
            visit(g, path, v)
        }

        path.add(u)
    }

    fun validArrangement(pairs: Array<IntArray>): Array<IntArray> {
        val g = constructGraph(pairs)
        val start = findStart(g)

        val path = mutableListOf<Int>()
        visit(g, path, start)

        path.reverse()

        return Array(path.size - 1) { i ->
            intArrayOf(path[i], path[i + 1])
        }
    }
}