#include<bits/stdc++.h>
# define int long long
# define rep(i, j, k) for (int i = j; i <= k; ++i)
# define inf 100000000LL
using namespace std;

int T, n, m, a[10005], plc[10005];
int hd[100005], to[100005], nxt[100005], c[100005], w[100005], etimer = 1;
int s, t, d[100005], instk[1000005], stk[1000005], l, r, cur[100005], now[100005];
void addedge(int u, int v, int ce, int we){to[++etimer] = v, nxt[etimer] = hd[u], hd[u] = etimer; c[etimer] = ce, w[etimer] = we;}
bool bfs()
{
    rep(i, 1, t) d[i] = inf;
    d[s] = 0, stk[l = r = 1] = s, instk[s] = 1;
    while (l <= r)
    {
        int u = stk[l++]; instk[u] = 0; //cerr << u << ' ' << d[u] << endl;
        for (int i = hd[u]; i; i = nxt[i]) if (c[i] && d[to[i]] > d[u] + w[i]) {d[to[i]] = d[u] + w[i]; if (!instk[to[i]]) stk[++r] = to[i], instk[to[i]] = 1;}
    }
    return d[t] <= inf / 10;
}
int dfs(int u, int f)
{
    if (u == t) return f;
    now[u] = 1;
    int ans = 0;
    for (int i = cur[u]; i && f; i = nxt[i])
    {
        cur[u] = i;
        if (!c[i] || d[to[i]] != d[u] + w[i] || now[to[i]]) continue;
        int x = dfs(to[i], min(f, c[i]));
        c[i] -= x, f -= x, c[i ^ 1] += x, ans += x;
    }
    now[u] = 0;
    return ans;
}
int dinic()
{
    int mincst = 0;
    while (bfs())
    {
    //    cerr << "gfddsf" << d[t] << endl;
        rep(i, 1, t) cur[i] = hd[i];
        int u = dfs(s, inf);// cerr << u << endl;
        mincst += u * d[t];
    }
    return mincst;
}
signed main()
{
   // freopen("a.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
    {
        memset(hd, 0, sizeof(hd)), memset(to, 0, sizeof(to)), memset(nxt, 0, sizeof(nxt)); etimer = 1;
        cin >> n >> m; s = n + m + 1, t = n + m + 2;
        rep(i, 1, n) cin >> a[i], addedge(i, t, a[i], 0), addedge(t, i, 0, 0), addedge(i, t, inf, 1), addedge(t, i, 0, -1);
        rep(i, 1, m) {int u, v; cin >> u >> v; addedge(s, n + i, 1, 0), addedge(n + i, s, 0, 0), addedge(n + i, u, 1, 0), plc[i] = etimer, addedge(u, n + i, 0, 0), addedge(n + i, v, 1, 0), addedge(v, n + i, 0, 0);}
        cout << dinic() << '\n';
        rep(i, 1, m) cout << 1 - c[plc[i]];
        cout << '\n';
    }
    return 0;
}