#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int v;
    int id;
};
struct Que {
    int l;
    int r;
    int id;
    const bool operator < (const Que &b) const {
        return l < b.l;
    }
};
int T;
int N;
int M;
int A[100009];
vector<Edge> oE[100009];
vector<Edge> E[100009];
int dfn[100009];
int low[100009];
int idx;
int stk[100009];
int tt;
int sid[100009];
int cnt;
vector<int> blk[100009];
int fa[100009];
int siz[100009];
Que Q[100009];
Que Ql[100009];
Que Qr[100009];
int cc;
int an[100009];
int ac;
int inv[100009];
int cnt0[100009];
int cnt1[100009];
int cnt2[100009];
int ans1[100009];
int ans2[100009];
int tans;
int tres;
int res[100009];

int Min (int a, int b) {
    return a < b ? a : b;
}

void Tarjan (int x, int fe) {
    dfn[x] = low[x] = ++idx, stk[++tt] = x;
    for (Edge v : oE[x])
        if (!dfn[v.v]) Tarjan(v.v, v.id), low[x] = Min(low[x], low[v.v]);
        else if (v.id != (fe ^ 1)) low[x] = Min(low[x], dfn[v.v]);
    if (dfn[x] == low[x]) {
        int v; cnt++;
        do {
            v = stk[tt--];
            sid[v] = cnt, blk[cnt].push_back(v);
        } while (v != x);
    }
}

int Get_Fa (int x) {
    if (fa[x] == x) return x;
    return fa[x] = Get_Fa(fa[x]);
}

int Max (int a, int b) {
    return a > b ? a : b;
}

void Dfs (int x, int p) {
    dfn[x] = ++idx, inv[idx] = x, siz[x] = 1;
    for (int v : blk[x]) {
        cnt0[A[v]]++;
        if (cnt0[A[v]] == 1) an[++ac] = A[v];
        tans = Max(tans, cnt0[A[v]]);
    }
    for (Edge v : E[x])
        if (v.v != p) {
            Dfs(v.v, x), siz[x] += siz[v.v];
            Q[++cc] = {dfn[v.v], dfn[v.v] + siz[v.v] - 1, (v.id >> 1) + 1};
        }
}

void Add (int x, int cnt[], int ans[], int &res) {
    for (int v : blk[x]) {
        ans[cnt[A[v]]]--, cnt[A[v]]++, ans[cnt[A[v]]]++;
        res = Max(res, cnt[A[v]]);
    }
}

void Delete (int x, int cnt[], int ans[], int &res) {
    for (int v : blk[x]) {
        if (ans[cnt[A[v]]] == 1 && res == cnt[A[v]]) res--;
        ans[cnt[A[v]]]--, cnt[A[v]]--, ans[cnt[A[v]]]++;
    }
}

void Get_Res (int l, int r, int ql, int qr) {
    int mid = l + r >> 1;
    int cntl = 0;
    int cntr = 0;
    int tl = l;
    int tr = r;
    int res1 = 0;
    int res2 = tans;

    if (ql > qr) return;
    for (int i = l; i <= r; i++) Add(inv[i], cnt1, ans1, res1), Delete(inv[i], cnt2, ans2, res2);
    for (int i = ql; i <= qr; i++)
        if (Q[i].r < mid) Ql[++cntl] = Q[i];
        else if (Q[i].l > mid) Qr[++cntr] = Q[i];
        else {
            while (tl < Q[i].l) {
                Delete(inv[tl], cnt1, ans1, res1), Add(inv[tl], cnt2, ans2, res2);
                tl++;
            }
            while (tr > Q[i].r) {
                Delete(inv[tr], cnt1, ans1, res1), Add(inv[tr], cnt2, ans2, res2);
                tr--;
            }
            res[Q[i].id] = res1 + res2 - tans;
        }
    for (int i = 1; i <= cntl; i++) Q[ql + i - 1] = Ql[i];
    for (int i = 1; i <= cntr; i++) Q[ql + cntl + i - 1] = Qr[i];
    for (int i = l; i <= r; i++)
        for (int v : blk[inv[i]]) {
            cnt1[A[v]] = 0;
            ans2[cnt2[A[v]]]--, cnt2[A[v]] = cnt0[A[v]], ans2[cnt2[A[v]]]++;
        }
    for (int i = 0; i <= r - l + 1; i++) ans1[i] = 0;
    Get_Res(l, mid - 1, ql, ql + cntl - 1), Get_Res(mid + 1, r, ql + cntl, ql + cntl + cntr - 1);
}

int main () {
    int a;
    int b;

    scanf("%d", &T);
    while (T--) {
        for (int i = 1; i <= N; i++) oE[i].clear(), sid[i] = dfn[i] = 0, cnt1[A[i]] = cnt2[A[i]] = 0;
        for (int i = 1; i <= cnt; i++) blk[i].clear(), E[i].clear(); cnt = 0;
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
        idx = 0;
        for (int i = 1; i <= M; i++) {
            res[i] = 0;
            scanf("%d%d", &a, &b);
            oE[a].push_back({b, idx++}), oE[b].push_back({a, idx++});
        }
        idx = 0;
        for (int i = 1; i <= N; i++)
            if (!dfn[i]) Tarjan(i, -1);
        for (int i = 1; i <= cnt; i++) fa[i] = i, dfn[i] = 0;
        for (int i = 1; i <= N; i++)
            for (Edge v : oE[i]) {
                a = Get_Fa(sid[i]), b = Get_Fa(sid[v.v]);
                if (a != b) {
                    fa[a] = b;
                    E[sid[i]].push_back({sid[v.v], v.id}), E[sid[v.v]].push_back({sid[i], v.id});
                }
            }
        idx = tres = 0;
        for (int i = 1; i <= cnt; i++)
            if (!dfn[i]) {
                cc = ac = tans = 0, Dfs(i, 0);
                for (int j = 1; j <= ac; j++) cnt2[an[j]] = cnt0[an[j]], ans2[cnt2[an[j]]]++;
                sort(Q + 1, Q + cc + 1);
                tres += tans, Get_Res(dfn[i], dfn[i] + siz[i] - 1, 1, cc);
                for (int j = 1; j <= ac; j++) ans2[cnt0[an[j]]] = 0, cnt0[an[j]] = 0;
            }
        for (int i = 1; i <= M; i++) {
            res[i] += tres;
            if (i < M) printf("%d ", res[i]);
            else printf("%d\n", res[i]);
        }
    }
    return 0;
}