可能这场比赛出现在各位眼前的时候普朗特先生已经不是镁帼的总统了。

出题人表示部分分并不知道如何给到位，因为拆点费用流可能稍微卡下子可能可以过。但是数据不知道为啥随机的这么强，把标算最大的点在本地卡到了1.3s。

考虑一点靠谱一点的做法。注意到一条边的边权是两端点的权值。那么，在一张二分图上找次最短增广路，一条增广路的长度=沿着它增广后总权值的变化 = 起点与终点的权值之和。

把左部和右部的点都按照点权大小排序，一次从未匹配的左部点开始dfs，标记一条路径上没有被访问过的右部点，标记用这种方法找出的所有可行的增广路的终点。

从找出的条增广路中挑出权值和最小的来增广。复杂度

赛时发现除了第一位同学是认真搞法，其余全部是 EK 卡过去的。破防了没卡死，全当大家图个乐吧。是出题人太菜了数据太水了

最后预祝大家NOIP2021顺利！

#include <bits/stdc++.h>
using namespace std;

const int SIZE_N = 1e5 + 5;
const int SIZE_M = 1e6 + 5;
const int inf = 0x7f7f7f7f;

int t, k, n, m, num, ans;
int head[SIZE_N], idx[SIZE_N], vis[SIZE_N];
int l[SIZE_N], r[SIZE_N], fa[SIZE_N], col[SIZE_N];

struct node {
int to, nxt;
} edge[SIZE_M << 1];

struct ver {
int w, idx;
    bool operator < (const ver &a) const {
        return w < a.w;
    }
} a[SIZE_N];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { 
            t = (s = buf) + fread(buf, 1, bufl, stdin);
            if (s == t) return EOF; 
        }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void addEdge(int u, int v) {
    edge[++ num].to = v, edge[num].nxt = head[u];
    head[u] = num;
}

void dfs(int u, int ff) {
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (!fa[v]) {
            fa[v] = u;
            if (!r[v]) col[v] = ff;
            else dfs(r[v], ff);
        }
    }
}

int solve() {
    memset(fa, 0, sizeof(fa));
    for (int i = 1; i <= n; ++ i) {
        if (!vis[i]) dfs(i, i);
    }
    int minn = inf, pos = -1;
    for (int i = 1; i <= n; ++ i) {
        if (!r[i] && fa[i]) {
            if (minn > a[i].w + a[col[i]].w)
                minn = a[i].w + a[col[i]].w, pos = i;
        }
    }
    if (pos == -1) return 0;
    ans += minn; int u = 0;
    for (u = pos; fa[u] != col[pos]; ) {
        r[u] = fa[u];
        int tmp = l[fa[u]];
        l[fa[u]] = u, u = tmp;
    }
    r[u] = col[pos], l[col[pos]] = u, vis[col[pos]] = 1;
    return 1;
}

void init() {
    ans = num = 0;
    memset(vis, 0, sizeof(vis));
    memset(head, 0, sizeof(head));
    memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r));
}

int main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    t = read();
    while (t --) {
        k = read(), n = read(), m = read();
        for (int i = 1; i <= n; ++ i) {
            a[i].w = read(), a[i].idx = i;
        }
        std::sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++ i) idx[a[i].idx] = i;
        for (int i = 1, u, v; i <= m; ++ i) {
            u = read(), v = read();
            addEdge(idx[u], idx[v]); 
        }
        int flag = 1;
        for (int i = 1; i <= k; ++ i) {
            if (!solve()) { flag = 0; break; }
        }
        if (!flag) puts("NONE");
        else printf("%d\n", ans);
        init();
    }
    return 0;
}