#include <cstdio>
#include <vector>
#include <algorithm>
int T, n, m, a[100010], ed[100010][2];
std::vector <int> e[100010], so[100010];
std::vector <std::pair<int, int>> E[100010];
int tm, dfn[100010], low[100010], stk[100010], tp, blk[100010], cnt;
int sz[100010], son[100010], val[100010], ans[100010];
void tarjan(int u, int f) {
	low[u] = dfn[u] = ++tm, stk[++tp] = u;
	for (auto v: E[u]) if (v.second != f) {
		if (!dfn[v.first]) tarjan(v.first, v.second), low[u] = std::min(low[u], low[v.first]);
		else low[u] = std::min(low[u], dfn[v.first]);
	}
	if (dfn[u] == low[u]) {
		++cnt;
		for (; stk[tp + 1] != u; --tp) blk[stk[tp]] = cnt, so[cnt].push_back(stk[tp]);
	}
}
void pre(int u, int f, int p) {
	sz[u] = so[u].size(), son[u] = 0, low[u] = p;
	for (int i = 0; i < sz[u]; ++i) val[tm + i] = a[so[u][i]];
	dfn[u] = tm, tm += sz[u];
	for (int v: e[u]) if (v != f) pre(v, u, p), 
		sz[u] += sz[v], sz[son[u]] < sz[v]? son[u] = v: 0;
}
struct Solver {
	int cnt[100010], res[100010], ans;
	void add(int x) {
		--res[cnt[x]], ++res[++cnt[x]];
		ans = std::max(ans, cnt[x]);
	}
	void del(int x) {
		if (--res[cnt[x]] == 0 && ans == cnt[x]) --ans;
		++res[--cnt[x]];
	}
}S1, S2;
void dfs(int u, int f) {
	for (int v: e[u]) if (v != f && v != son[u]) {
		dfs(v, u);
		for (int i = dfn[v]; i < dfn[v] + sz[v]; ++i)
			S1.del(val[i]), S2.add(val[i]);
	}
	if (!son[u]) {
		for (int i: so[u]) S1.add(a[i]), S2.del(a[i]);
		ans[u] = S1.ans + S2.ans;
		return;
	}
	dfs(son[u], u);
	for (int i = dfn[u]; i < dfn[son[u]]; ++i) 
		S1.add(val[i]), S2.del(val[i]);
	for (int i = dfn[son[u]] + sz[son[u]]; i < dfn[u] + sz[u]; ++i) 
		S1.add(val[i]), S2.del(val[i]);
	ans[u] = S1.ans + S2.ans;
}
int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i) scanf("%d", a + i);
		for (int i = 1; i <= m; ++i) {
			int u, v;
			scanf("%d%d", &u, &v);
			ed[i][0] = u, ed[i][1] = v;
			if (u != v) E[u].emplace_back(v, i), E[v].emplace_back(u, i);
		}
		for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);
		for (int i = 1; i <= m; ++i) {
			int u = blk[ed[i][0]], v = blk[ed[i][1]];
			if (u != v) e[u].push_back(v), e[v].push_back(u);
		}
		int tot = 0;
		for (int i = 1; i <= cnt; ++i) if (!sz[i]) {
			tm = 1, pre(i, 0, i);
			for (int j = 1; j <= sz[i]; ++j) S2.add(val[j]);
			dfs(i, 0), tot += S1.ans;
			for (int j = 1; j <= sz[i]; ++j) S1.cnt[val[j]] = 0;
			for (int j = 0; j <= S1.ans; ++j) S1.res[j] = 0;
			S1.ans = 0;
		}
		for (int i = 1; i <= m; ++i) {
			int u = blk[ed[i][0]], v = blk[ed[i][1]];
			int res = tot;
			if (u != v) {
				if (sz[u] < sz[v]) std::swap(u, v);
				res += ans[v] - ans[low[v]];
			}
			printf("%d%c", res, " \n"[i == m]);
		}
		for (int i = 1; i <= n; ++i) dfn[i] = low[i] = 0, E[i].clear();
		for (int i = 1; i <= cnt; ++i) sz[i] = 0, e[i].clear(), so[i].clear();
		cnt = 0;
	}
}