fun roadsAndLibraries(
    n: Int,
    c_lib: Int,
    c_road: Int,
    cities: Array<Array<Int>>
): Long {
    if (c_lib<=c_road) return (c_lib.toLong()*n)
    val nodes = (1..n).map {Node(it)}
    for (edge in cities) {
        connectNodes(nodes[edge[0]-1], nodes[edge[1]-1])
    }
    val groups = mutableSetOf<Set<Node>>()
    val visited = mutableSetOf<Node>()
    for (i in nodes.indices) {
        if (visited.contains(nodes[i])) continue
        val reachable = findReachable(nodes[i])
        groups.add(reachable)
        visited.addAll(reachable)
    }
    val costOfLib = c_lib*groups.size.toLong()
    val costOfRoads = c_road*groups.map {it.size.toLong() - 1}
                            .sum()
    
    return costOfLib + costOfRoads
}

class Node(val num: Int) {
    val connections = mutableSetOf<Node>()
}

fun findReachable(node:Node): Set<Node> {
    val visited = mutableSetOf<Node>()
    val queue: Queue<Node> = LinkedList()
    queue.add(node)
    while (!queue.isEmpty()) {
        val next = queue.remove()
        if (!visited.contains(next)) {
            visited.add(next)
            for (n in next.connections) {
                if (!visited.contains(n)) {
                    queue.add(n)
                }
            }
        }
    }
    return visited
}

fun connectNodes(a:Node, b:Node) {
    a.connections.add(b)
    b.connections.add(a)
}