class DisjointSetUnion {

    companion object {

        const val EMPTY_SLOT = Int.MIN_VALUE
    }

    val elemParent: IntArray
    val rank: IntArray
    var setCount = 0

    constructor(initialCapacity: Int) {
        elemParent = IntArray(initialCapacity).apply { fill(EMPTY_SLOT) }
        rank = IntArray(initialCapacity)
    }

    constructor(initialSetsCount: Int, initSets: Boolean) {
        elemParent = IntArray(initialSetsCount)
        rank = IntArray(initialSetsCount)
        setCount = initialSetsCount
        for (i in 0 until initialSetsCount) {
            elemParent[i] = i
            rank[i] = 0
        }
    }

    inline fun makeSet(newElem: Int) {
        ++setCount
        elemParent[newElem] = newElem
        rank[newElem] = 0
    }

    fun find(elem: Int): Int {
        if (elemParent[elem] == EMPTY_SLOT) {
            throw Exception()
        }

        var element = elem
        var root = element
        while (root != elemParent[root]) {
            root = elemParent[root]
        }

        // Path compression
        while (element != elemParent[element]) {
            val prevElem = element;
            element = elemParent[element]
            elemParent[prevElem] = root
        }
        return root
    }

    fun unite(elem1: Int, elem2: Int): Int {
        if (elemParent[elem1] == EMPTY_SLOT || elemParent[elem2] == EMPTY_SLOT) {
            throw Exception()
        }

        var maxRankElem = find(elem1)
        var minRankElem = find(elem2)
        if (maxRankElem == minRankElem) {
            return maxRankElem
        }
        if (rank[maxRankElem] < rank[minRankElem]) {
            // Swap
            val tmp = maxRankElem
            maxRankElem = minRankElem
            minRankElem = tmp
        }

        // Rank heuristic
        elemParent[minRankElem] = maxRankElem;
        if (rank[maxRankElem] == rank[minRankElem]) {
            ++rank[maxRankElem]
        }
        --setCount
        return maxRankElem // return parent both elements
    }
}