for (int i = wins[0]; i <= wins[0] + cnt; i++){         
            if (i < maxW + 1) {
            flag = 0;
            continue;
            }

            updateC(flag, i);
            if (go() == M) {
                ans = i; break;
            }
            flag = 1;
        }

for (int i = maxW + 1; i <= wins[0] + cnt; i++){
            /*
            if (i < maxW + 1) {
            flag = 0;
            continue;
            }
            */
            updateC(flag, i);
            if (go() == M) {
                ans = i; break;
            }
            flag = 1;
        }

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct Edge {
    int to, c, f;
    Edge(int to, int c, int f) : to(to), c(c), f(f) {}
    Edge* r;
    int pflow() { return c - f; }
    void push(int val) {
        f += val, r->f -= val;
    }
};
int S, T, C, N, M, wins[20], maxC, maxF, maxW, cnt, ans;
Edge* idx[20];
vector<vector<Edge*>> adj;
void addE(int a, int b, int c) {
    Edge* ab = new Edge(b, c, 0), *ba = new Edge(a, 0, 0);
    ab->r = ba;
    ba->r = ab;
    adj[a].push_back(ab);
    adj[b].push_back(ba);
    if (b == T) idx[a - M] = ab;
}
void updateC(int m, int val) {
    maxC = 0;
    for (int i = M; i < N + M; i++) {
        int newC = val - wins[i - M] - (i != M);
        if (!m) addE(i, T, newC);
        else idx[i - M]->c = newC;
    }
}
int go() {
    while (1) {
        vector<pair<int, int>> p(T + 5, make_pair(-1, -1));
        queue<int> q;
        q.push(S); p[S] = make_pair(S, S);
        while (!q.empty() && p[T].first == -1) {
            int now = q.front(); q.pop();
            for (int i = 0; i < adj[now].size(); i++) {
                Edge* nv = adj[now][i];
                if (nv->pflow() > 0 && p[nv->to].first == -1)
                    q.push(nv->to), p[nv->to] = make_pair(now, i);
            }
        }
        if (p[T].first == -1) {
            break;
        }
        int minF = 1;
        for (int i = T; i != S; i = p[i].first)
            adj[p[i].first][p[i].second]->push(minF);
        maxF += minF;
    }
    return maxF;
}
int main() {
    scanf("%d", &C);
    while (C--) {
        scanf("%d %d", &N, &M);

        memset(wins, 0, sizeof(wins));
        maxC = maxF = maxW = cnt = ans = 0;
        adj.clear();

        S = N + M + 5, T = N + M + 10;
        adj.resize(T + 5);

        for (int i = 0; i < N; i++) {
            scanf("%d", &wins[i]);
            if (i) maxW = max(maxW, wins[i]);
        }
        for (int i = 0, a, b; i < M; i++) {
            scanf("%d %d", &a, &b);
            if (!a || !b) cnt++;
            addE(S, i, 1);
            addE(i, M + a, 1), addE(i, M + b, 1);
        }
        int flag = 0; ans = -1;
        for (int i = maxW + 1; i <= wins[0] + cnt; i++){
            /*
            if (i < maxW + 1) {
            flag = 0;
            continue;
            }
            */
            updateC(flag, i);
            if (go() == M) {
                ans = i; break;
            }
            flag = 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}