#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e6 + 2, LG = 20, blocksize = 550, inf = 1e18;
int t, n, m, a[maxn], x[maxn], y[maxn], low[maxn], num[maxn], tt, par[maxn], sz[maxn], nxt[maxn];
int in[maxn], in_cnt[maxn], out[maxn], out_cnt[maxn], mode_in, mode_out, global, cur, inc[maxn];
bool used[maxn], visited[maxn];
vector<int> adj[maxn], ok[maxn];
int find_set (int u)
{
    if (par[u] < 0) return u;
    return (par[u] = find_set(par[u]));
}
void union_set (int u, int v)
{
    int pu = find_set(u), pv = find_set(v);
    if (pu == pv) return;
    if (par[pu] > par[pv]) swap(pu, pv);
    par[pu] += par[pv];
    par[pv] = pu;
    for (int i : ok[pv]) ok[pu].push_back(i);
    ok[pv].clear();
}
void predfs (int u)
{
    low[u] = num[u] = ++tt;
    for (int i : adj[u])
    {
        if (used[i]) continue;
        used[i] = true;
        int v = x[i] ^ y[i] ^ u;
        if (!num[v])
        {
            predfs(v);
            low[u] = min(low[u], low[v]);
            if (low[v] <= num[u]) union_set(u, v);
        }
        else low[u] = min(low[u], num[v]);
    }
}
void dfs (int u, int p)
{
    visited[u] = true;
    for (int i : ok[u])
    {
        out_cnt[out[a[i]]]--;
        out[a[i]]++;
        out_cnt[out[a[i]]]++;
        mode_out = max(mode_out, out[a[i]]);
    }
    sz[u] = ok[u].size();
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p) continue;
        //cout << u << " " << v << endl;
        dfs(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[nxt[u]]) nxt[u] = v;
    }
}
void add (int u, int p)
{
    for (int i : ok[u])
    {
        in_cnt[in[a[i]]]--;
        in[a[i]]++;
        in_cnt[in[a[i]]]++;
        mode_in = max(mode_in, in[a[i]]);

        out_cnt[out[a[i]]]--;
        out[a[i]]--;
        out_cnt[out[a[i]]]++;
        if (out_cnt[mode_out] == 0) mode_out--;
    }
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p) continue;
        add(v, u);
    }
}
void del (int u, int p)
{
    for (int i : ok[u])
    {
        out_cnt[out[a[i]]]--;
        out[a[i]]++;
        out_cnt[out[a[i]]]++;
        mode_out = max(mode_out, out[a[i]]);

        in_cnt[in[a[i]]]--;
        in[a[i]]--;
        in_cnt[in[a[i]]]++;
        if (in_cnt[mode_in] == 0) mode_in--;
    }
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p) continue;
        del(v, u);
    }
}
void clear (int u, int p)
{
    for (int i : ok[u])
    {
        in_cnt[in[a[i]]]--;
        in[a[i]]--;
        in_cnt[in[a[i]]]++;
        if (in_cnt[mode_in] == 0) mode_in--;
    }
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p) continue;
        clear(v, u);
    }
}
void sack (int u, int p, int e)
{
    int nxt_edge = 0;
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p) continue;
        if (v == nxt[u])
        {
            nxt_edge = i;
            continue;
        }
        sack(v, u, i);
        del(v, u);
    }
    if (nxt[u] != 0) sack(nxt[u], u, nxt_edge);
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p || v == nxt[u]) continue;
        add(v, u);
    }
    for (int i : ok[u])
    {
        in_cnt[in[a[i]]]--;
        in[a[i]]++;
        in_cnt[in[a[i]]]++;
        mode_in = max(mode_in, in[a[i]]);

        out_cnt[out[a[i]]]--;
        out[a[i]]--;
        out_cnt[out[a[i]]]++;
        if (out_cnt[mode_out] == 0) mode_out--;
    }
    if (e != 0) inc[e] = mode_in + mode_out - cur;
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--)
    {
        //cout << '\n';
        cin >> n >> m;
        tt = 0; global = 0;
        for (int i = 1; i <= n; i++)
        {
            low[i] = num[i] = 0;
            par[i] = -1;
            visited[i] = false;
            adj[i].clear();
            ok[i] = {i};
            nxt[i] = 0;
            cin >> a[i];
        }
        for (int i = 1; i <= m; i++)
        {
            used[i] = false;
            inc[i] = 0;
            cin >> x[i] >> y[i];
            adj[x[i]].push_back(i);
            adj[y[i]].push_back(i);
        }
        for (int i = 1; i <= n; i++)
        {
            if (!num[i]) predfs(i);
        }
        for (int i = 1; i <= n; i++) adj[i].clear();
        for (int i = 1; i <= m; i++)
        {
            x[i] = find_set(x[i]); y[i] = find_set(y[i]);
            if (x[i] != y[i])
            {
                //cout << x[i] << " " << y[i] << '\n';
                adj[x[i]].push_back(i);
                adj[y[i]].push_back(i);
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i] && par[i] < 0)
            {
                assert(mode_in == 0 && mode_out == 0);
                dfs(i, 0);
                global += mode_out;
                cur = mode_out;
                sack(i, 0, 0);
                clear(i, 0);
                //cout << '\n';
            }
        }
        for (int i = 1; i <= m; i++) cout << inc[i] + global << " ";
        cout << '\n';
        //for (int i = 1; i <= m; i++) cout << inc[i] << " ";
        //cout << '\n';
    }
}