#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {
  x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
  return x += y, x >= mod && (x -= mod), x;
}

struct FastMod {
  ull b, m;
  FastMod(ull b = 1) : b(b), m(ull((LL(1) << 64) / b)) {}
  ull reduce(ull a) {
    ull q = ull((LL(m) * a) >> 64);
    ull r = a - q * b; // can be proven that 0 <= r < 2 * b
    return r >= b ? r - b : r;
  }
} R;

// ---------- templates above ----------

constexpr int K = 17;
constexpr int N = 1e5 + 5;

vector<pii> e[N];
int n, m, a[N], vis[N], pic[N], f[N];
int tot, res[N], ans[N];
struct bucket {
  int maj, buc[N], occ[N], cnt, ap[N], vis[N];
  void init() {
    occ[0] = N;
    for(int i = 0; i <= maj; i++) occ[i] = 0;
    for(int i = 1; i <= cnt; i++) vis[ap[i]] = buc[ap[i]] = 0;
    cnt = maj = 0;
  }
  void upd(int x, int v) {
    if(!vis[x]) ap[++cnt] = x, vis[x] = 1;
    if(v == 1) {
      occ[buc[x]]--, occ[++buc[x]]++;
      if(occ[maj + 1]) maj++;
    }
    else {
      occ[buc[x]]--, occ[--buc[x]]++;
      if(!occ[maj]) maj--;
    }
  }
} in, out;

int dn, dfn[N], rev[N], mi[K][N];
int fa[N], sz[N], son[N];
int get(int x, int y) {
  return dfn[x] < dfn[y] ? x : y;
}
int lca(int u, int v) {
  if(u == v) return u;
  if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
  int d = __lg(v - u++);
  return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
void dfs(int id, int ff) {
  // cerr << "dfs " << id << " " << ff << endl;
  vis[id] = sz[id] = 1;
  dfn[id] = ++dn, rev[dn] = id;
  mi[0][dn] = fa[id] = ff;
  in.upd(a[id], 1);
  for(pii _ : e[id]) {
    int it = _.first;
    if(vis[it]) continue;
    pic[_.second] = 1, dfs(it, id);
    sz[id] += sz[it];
    if(sz[son[id]] < sz[it]) son[id] = it;
  }
}
void count(int x, int v) {
  for(int p = dfn[x]; p < dfn[x] + sz[x]; p++) {
    in.upd(a[rev[p]], v);
    out.upd(a[rev[p]], -v);
  }
}
void dfs2(int id, int res) {
  // cerr << "dfs2 " << id << " " << fa[id] << " " << son[id] << " " << res << endl;
  int sonid = 0;
  for(pii _ : e[id]) {
    int it = _.first, eid = _.second;
    if(!pic[eid] || it == fa[id]) continue;
    if(it == son[id]) {sonid = eid; continue;}
    dfs2(it, res), f[id] += f[it];
    if(!f[it]) ans[eid] = tot - res + in.maj + out.maj;
    count(it, -1);
  }
  if(son[id]) {
    dfs2(son[id], res), f[id] += f[son[id]];
    if(!f[son[id]]) ans[sonid] = tot - res + in.maj + out.maj;
  }
  for(pii _ : e[id]) {
    int it = _.first;
    if(pic[_.second] && it != fa[id] && it != son[id]) count(it, 1);
  }
  in.upd(a[id], 1), out.upd(a[id], -1);
}
void solve() {
  cin >> n >> m, dn = tot = 0;
  for(int i = 1; i <= n; i++) {
    vis[i] = f[i] = son[i] = 0;
    e[i].clear();
  }
  for(int i = 1; i <= m; i++) pic[i] = ans[i] = 0;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back({v, i});
    e[v].push_back({u, i});
  }
  for(int i = 1; i <= n; i++) {
    if(!vis[i]) {
      in.init(), dfs(i, 0);
      tot += res[i] = in.maj;
    }
  }
  for(int i = 1; i <= __lg(n); i++) {
    for(int j = 1; j + (1 << i) - 1 <= n; j++) {
      mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
    }
  }
  for(int i = 1; i <= n; i++) {
    for(pii _ : e[i]) {
      int it = _.first;
      if(i > it || pic[_.second]) continue;
      f[i]++, f[it]++, f[lca(i, it)] -= 2;
    }
  }
  for(int i = 1; i <= n; i++) {
    if(fa[i]) continue;
    in.init(), out.init();
    for(int p = dfn[i]; p < dfn[i] + sz[i]; p++) out.upd(a[rev[p]], 1);
    dfs2(i, res[i]);
  }
  for(int i = 1; i <= m; i++) {
    if(ans[i]) cout << ans[i];
    else cout << tot;
    if(i == m) cout << '\n';
    else cout << ' ';
  }
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  cin >> T;
  while(T--) solve();
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/