Mansão do Mamão

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 2e18 + 10;
vector<vector<int>> grafo;
vector<array<int, 3>> dp;
vector<int> val, marc;
vector<int> pai, sub;


int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
bool une(int x, int y)
{
    x = find(x); y = find(y);
    if (x == y) return 0;
    if (sub[x] < sub[y]) swap(x, y);
    pai[y] = x; sub[x] += sub[y];
    return 1;
}


void dfs(int v, int p)
{
    dp[v] = {0, val[v], 0};

    int minMuda = INF;
    for (auto viz : grafo[v])
    {
        if (viz == p) continue;
        dfs(viz, v);
        dp[v][1] += min(dp[viz][1], dp[viz][2]);
        dp[v][2] += min(dp[viz][0], dp[viz][1]);
        minMuda = min(minMuda, dp[viz][1] - min(dp[viz][0], dp[viz][1]));
    }

    dp[v][0] = dp[v][2] + (marc[v] ? 0 : minMuda);
}

int bt(int id, const vector<pair<int, int>> &edges)
{
    if (id == edges.size())
    {
        dfs(1, 1);
        return min(dp[1][0], dp[1][1]);
    }

    auto [X, Y] = edges[id];
    int auxX = val[X], auxY = val[Y];
    int resp = INF;
    resp = min(resp, bt(id+1, edges));
    val[X] = 0; marc[Y]++;
    resp = min(resp, bt(id+1, edges)+auxX);
    val[X] = auxX; marc[Y]--;
    val[Y] = 0; marc[X]++;
    resp = min(resp, bt(id+1, edges)+auxY);
    val[Y] = auxY; marc[X]--;

    return resp;
}

void solve()
{
    int N, M;
    cin >> N >> M;
    pai.resize(N+1); iota(pai.begin(), pai.end(), 0);
    sub.resize(N+1); fill(sub.begin(), sub.end(), 1);

    val.resize(N+1);
    for (int i = 1; i <= N; i++) cin >> val[i];
    grafo.clear(); grafo.resize(N+1); dp.resize(N+1); marc.clear(); marc.resize(N+1);
    vector<pair<int, int>> edges;
    for (int i = 1; i <= M; i++)
    {
        int X, Y;
        cin >> X >> Y;
        if (une(X, Y))
            grafo[X].push_back(Y), grafo[Y].push_back(X);
        else
            edges.emplace_back(X, Y);
    }

    cout << bt(0, edges) << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T; cin >> T;
    while (T--) solve();
}