class Solution {
    fun longestCommonPrefix(words: Array<String>): IntArray {
        val n = words.size
        val answer = IntArray(n)
        if (n <= 1) return answer

        val lcp = IntArray(n - 1)
        for (i in 0 until n - 1) {
            lcp[i] = commonPrefixLength(words[i], words[i + 1])
        }

        val prefixMax = IntArray(n - 1)
        prefixMax[0] = lcp[0]
        for (i in 1 until n - 1) {
            prefixMax[i] = maxOf(prefixMax[i - 1], lcp[i])
        }

        val suffixMax = IntArray(n - 1)
        suffixMax[n - 2] = lcp[n - 2]
        for (i in n - 3 downTo 0) {
            suffixMax[i] = maxOf(suffixMax[i + 1], lcp[i])
        }

        for (i in 0 until n) {
            var maxLen = 0
            if (i - 2 >= 0) {
                maxLen = maxOf(maxLen, prefixMax[i - 2])
            }
            if (i + 1 <= n - 2) {
                maxLen = maxOf(maxLen, suffixMax[i + 1])
            }
            if (i in 1 until n - 1) {
                val merged = commonPrefixLength(words[i - 1], words[i + 1])
                maxLen = maxOf(maxLen, merged)
            }
            answer[i] = maxLen
        }

        return answer
    }

    private fun commonPrefixLength(a: String, b: String): Int {
        val minLen = minOf(a.length, b.length)
        var i = 0
        while (i < minLen && a[i] == b[i]) {
            i++
        }
        return i
    }
} 

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