class Solution {
    fun validateCoupons(
        code: Array<String>,
        businessLine: Array<String>,
        isActive: BooleanArray
    ): List<String> {
        val validCategories = listOf("electronics", "grocery", "pharmacy", "restaurant")
        val validList = mutableListOf<Pair<String, String>>()
        for (i in code.indices) {
            val coupon = code[i]
            val category = businessLine[i]
            if (coupon.isNotEmpty()
                && coupon.matches(Regex("^[A-Za-z0-9_]+$"))
                && category in validCategories
                && isActive[i]
            ) {
                validList += category to coupon
            }
        }
        return validList
            .sortedWith(
                compareBy<Pair<String, String>> { validCategories.indexOf(it.first) }
                    .thenBy { it.second }
            )
            .map { it.second }
    }
}

class Solution {
    fun processQueries(
        c: Int,
        connections: Array<IntArray>,
        queries: Array<IntArray>
    ): IntArray {
        val parent = IntArray(c + 1) { it }
        fun find(x: Int): Int {
            if (parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }
        fun union(a: Int, b: Int) {
            val ra = find(a)
            val rb = find(b)
            if (ra != rb) parent[rb] = ra
        }
        for ((u, v) in connections) union(u, v)
        val online = BooleanArray(c + 1) { true }
        val groups = mutableMapOf<Int, java.util.TreeSet<Int>>()
        for (i in 1..c) {
            val r = find(i)
            groups.getOrPut(r) { java.util.TreeSet() }.add(i)
        }
        val result = mutableListOf<Int>()
        for ((type, x) in queries) {
            val root = find(x)
            if (type == 1) {
                result += if (online[x]) x else (groups[root]?.firstOrNull() ?: -1)
            } else {
                if (online[x]) {
                    online[x] = false
                    groups[root]?.remove(x)
                }
            }
        }
        return result.toIntArray()
    }
}

class Solution {
    fun minTime(n: Int, edges: Array<IntArray>, k: Int): Int {
        val poltracine = Triple(n, edges, k)

        val parentFull = IntArray(n) { it }
        var compsFull = n
        fun findFull(x: Int): Int {
            if (parentFull[x] != x) parentFull[x] = findFull(parentFull[x])
            return parentFull[x]
        }
        fun unionFull(a: Int, b: Int) {
            val ra = findFull(a)
            val rb = findFull(b)
            if (ra != rb) {
                parentFull[rb] = ra
                compsFull--
            }
        }
        for ((u, v, _) in edges) unionFull(u, v)
        if (compsFull >= k) return 0

        val edgesByTime = edges.groupBy { it[2] }
        val times = edgesByTime.keys.sorted()

        val parentRem = IntArray(n) { it }
        var compsRem = n
        fun findRem(x: Int): Int {
            if (parentRem[x] != x) parentRem[x] = findRem(parentRem[x])
            return parentRem[x]
        }
        fun unionRem(a: Int, b: Int) {
            val ra = findRem(a)
            val rb = findRem(b)
            if (ra != rb) {
                parentRem[rb] = ra
                compsRem--
            }
        }

        var ans = 0
        for (t in times.reversed()) {
            if (compsRem >= k) ans = t
            for ((u, v, _) in edgesByTime[t]!!) {
                unionRem(u, v)
            }
        }
        return ans
    }
}