#include <vector>
using namespace std;

class Solution {
  public:

    class DSU {
      public:
        vector<int> parent, rank;
        int components;
        DSU(int n) : parent(n + 1), rank(n + 1, 1), components(n) {
            for (int i = 1; i <= n; ++i)
                parent[i] = i;
        }
        DSU(const DSU& other) : parent(other.parent), rank(other.rank),
            components(other.components) {}
        int find(int x) {
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }
        bool unite(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y)
                return false;
            if (rank[x] < rank[y])
                swap(x, y);
            parent[y] = x;
            if (rank[x] == rank[y])
                rank[x]++;
            components--;
            return true;
        }
    };

    int maxRemovableEdges(int n, vector<vector<int>>& edges) {
        if (n == 1)
            return edges.size();

        DSU type3_dsu(n);
        for (const auto& e : edges) {
            int type = e[0], u = e[1], v = e[2];
            if (type == 3)
                type3_dsu.unite(u, v);
        }
        int c3_components = type3_dsu.components;

        DSU alice = type3_dsu;
        for (const auto& e : edges) {
            int type = e[0], u = e[1], v = e[2];
            if (type == 1)
                alice.unite(u, v);
        }
        if (alice.components != 1)
            return -1;

        DSU bob = type3_dsu;
        for (const auto& e : edges) {
            int type = e[0], u = e[1], v = e[2];
            if (type == 2)
                bob.unite(u, v);
        }
        if (bob.components != 1)
            return -1;

        int min_edges = (n - 1) + (c3_components - 1);
        return edges.size() - min_edges;
    }

};

采用QwQ-32B Q6_K（20250312版本）通过llama.cpp AI生成，参数根据readme和论文建议进行设置。

prompt：以下是一道算法题，请你用尽可能低的时间和空间复杂度，尽可能短的代码，在符合题目要求的情况下用C++20完成这道题，并给出解题思路，\n代表换行：“描述\n在一个神奇的动物牛国度中，生活着许多有趣的动物。Alice 和 Bob 是这个国度中的两位勇士，他们决定一起展开一次探险之旅。他们面前是一个神秘的无向图，图中有 n 个节点和 3 种类型的边：\n类型 1：只有 Alice 可以经过的边。\n类型 2：只有 Bob 可以经过的边。\n类型 3：Alice 和 Bob 都可以经过的边。\n他们想要确保无论从哪个节点出发，Alice 和 Bob 都能够遍历到所有其他节点。为了达到这个目标，他们可以删除一些边。删除边后，他们希望仍然能够完成完全的探险之旅。\n请你编写一个函数 int maxRemovableEdges(int n, vector<vector<int>>& edges)，来帮助 Alice 和 Bob 计算可以删除的最大边数。如果无论如何删除边，Alice 和 Bob 仍然无法完全遍历图，则返回 -1。\n函数输入参数：\nn：一个整数，表示节点的个数。\nedges：一个二维整数数组，表示边的信息。每个元素 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。边的类型 typei 可以是 1、2 或 3，正好对应上述三种情况。\n函数输出：\n返回一个整数，表示可以删除的最大边数。如果无论如何删除边，Alice 和 Bob 仍然无法完全遍历图，则返回 -1。\n备注\n1 <= n <= 10^5\n1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)\nedges[i].length == 3\n1 <= edges[i][0] <= 3\n1 <= edges[i][1] < edges[i][2] <= n\n所有元组 (typei, ui, vi) 互不相同\n示例\n输入：3,[[1, 1, 2],[2, 2, 3],[3, 1, 3],[1, 1, 3]]，输出：1\n输入：4,[[3, 1, 2],[3, 2, 3],[1, 1, 3],[1, 2, 4],[1, 1, 2],[2, 3, 4]]，输出：2\n输入：5,[[3, 1, 2],[3, 2, 3],[3, 3, 4],[3, 4, 5],[1, 1, 3],[1, 2, 4],[1, 3, 5]]，输出：3”