class UF {
private:
    // 连通分量个数
    int count;
    // 存储每个节点的父节点
    int *parent;
public:
    // n 为图中节点的个数
    UF(int n) {
        count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
        // 第二种路径压缩的 find 方法-效率更高
        // if (parent[x] != x) {
        //     parent[x] = find(parent[x]);
        // }
        // return parent[x];
    }
    /* 将 p 和 q 连接 */
    void unionTwo(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot)
            return;
        parent[pRoot] = qRoot;
        count--;
    }
    /* 判断 p 和 q 是否连通 */
    bool connected(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        return pRoot == qRoot;
    }
    /* 返回图中有多少个连通分量 */
    int countN() {
        return count;
    }
};

class Prim {
    public:
        Prim(vector<vector<vector<int>>>& points) {
            graph = points;
            int n = graph.size();
            inMST.resize(n);

            inMST[0] = true;
            cut(0);
            while (!pq.empty()) {
                vector<int> edge = pq.top();
                pq.pop();
                int to = edge[1];
                int weight = edge[2];
                if (inMST[to]) {
                    continue;
                }
                weightSum += weight;
                inMST[to] = true;
                cut(to);
            }
        }
        // 将 s 的横切变加入优先队列
        void cut(int s) {
            for (auto& node : graph[s]) {
                int to = node[1];
                if (inMST[to]) {
                    continue;
                }
                pq.push(node);
            }
        }
        // 最小生成树的权重和
        int getweightSum() {
            return weightSum;
        }
        // 判断最小生成树是否包含图中所有节点
        bool allConnect() {
            for (int i = 0; i < inMST.size(); i++) {
                if (!inMST[i]) {
                    return false;
                }
            }
            return true;
        }

        struct cmp //重写仿函数
        {
            bool operator() (vector<int>& a, vector<int>& b)
            {
                return a[2] > b[2]; //大顶堆
            }
        };
    private:
        // 核心数据结构，存储「横切边」的优先级队列
        priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
        // 类似 visited 数组的作用，记录哪些节点已经成为最小生成树的一部分
        vector<bool> inMST;
        // 记录最小生成树的权重和
        int weightSum = 0;
        // graph 是用邻接表表示的一幅图，
        // graph[s] 记录节点 s 所有相邻的边，
        // 三元组 int[]{from, to, weight} 表示一条边
        vector<vector<vector<int>>> graph;
};

vector<int> nextGreaterElement(vector<int> nums) {
    int n = nums.size();
    // 存放答案的数组
    vector<int> res(n);
    stack<int> s;
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的更大元素
        res[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return res;
}