#include <stdio.h>
#include <vector>
#include <queue>
#include <memory.h>
#define pb push_back
using namespace std;


int S, E, n, m;
int win[15];
int flow[200][200] = { 0 };
int ary[200][200];
int goal, res = 0;
vector <vector <int> >vec;
vector <int> parent;

int netflow()
{

    int a, b;
    queue <int> que;
    while (1)
    {
        vector <bool> chk(m + n + 5, false);
        que.push(S);
        while (!que.empty())
        {
            a = que.front(); que.pop();
            for (int i = 0; i<vec[a].size(); i++)
            {
                b = vec[a][i];
                if (!chk[b] && ary[a][b] - flow[a][b] > 0)
                {
                    que.push(b);
                    chk[b] = true;
                    parent[b] = a;
                }
            }
        }
        if (!chk[E])break;
        res++;
        for (int v = E; v != S; v = parent[v])
        {
            flow[parent[v]][v] += 1;
            flow[v][parent[v]] -= 1;
        }
    }
    return res;
}

bool isWin(int goal)
{
    int max;
    for (int i = 1; i <= n; i++)
    {
        max = (i == 1 ? goal : goal - 1);
        ary[m + i][E] = max-win[i];
    }
    return netflow() == m; // goal로 모두 매칭이 가능한가?
}
int main()
{
    int t, a, b;
    scanf("%d", &t);
    while (t--)
    {
        memset(flow, 0, sizeof(flow));
        goal = -1;
        res = 0;
        scanf("%d %d", &n, &m);
        vec.resize(m + n + 5);
        parent.resize(m + n + 5);
        S = 0, E = m + n + 1;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &win[i]);
            if (goal == -1 || win[i] > goal)
            {
                goal = win[i];
                if (i != 1)goal++;
            }
            vec[m + i].pb(E);
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%d %d", &a, &b);
            vec[i].pb(m + a + 1); vec[i].pb(m + b + 1); //  경기->선수 A,B
            ary[i][m + a + 1] = 1; ary[i][m + b + 1] = 1; 
            vec[m + a + 1].pb(i); vec[m + b + 1].pb(i); // 선수A,B -> 경기
            vec[S].pb(i); // 소스->경기
            ary[S][i] = 1;
        }
        while (!isWin(goal))
        {
            goal++;
            if (goal > win[1] + m+1)break;
        }

        if (goal > win[1]+m || goal != flow[1+m][E]+win[1]  )
            printf("-1\n");
        else
        printf("%d\n", goal);

    }
    return 0;
}