// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
vector<pii> G[N];
int dfn[N], low[N];
int stk[N], top, cnt;
int sccID[N];
int assassass;
bool instack[N];
void tarjan(int x, int fa, int pid)
{
	stk[top++] = x;
	dfn[x] = low[x] = ++assassass;
	instack[x] = 1;
	for (auto [y, id] : G[x])
	{
		if (y == x)
			continue;
		if (id == pid)
			continue;
		if (!dfn[y])
		{
			tarjan(y, x, id);
			low[x] = min(low[x], low[y]);
		}
		else if (instack[y])
			low[x] = min(low[x], dfn[y]);
	}
	if (low[x] == dfn[x])
	{
		cnt++;
		while (true)
		{
			int p = stk[--top];
			instack[p] = 0;
			sccID[p] = cnt;
			if (p == x)
				break;
		}
	}
}
vector<pii> newG[N];

int hson[N], siz[N];

void dfs0(int x, int f)
{
	siz[x] = 1;
	for (auto [y, id] : newG[x])
	{
		if (y == f)
			continue;
		dfs0(y, x);
		siz[x] += siz[y];
		if (siz[hson[x]] < siz[y])
			hson[x] = y;
	}
}
struct Color
{
	int cnt[N], cntSiz[N];
	int maxCnt;
	int tot;
	void add(int c)
	{
		tot++;
		cntSiz[cnt[c]]--;
		cnt[c]++;
		cntSiz[cnt[c]]++;
		if (maxCnt < cnt[c])
			maxCnt++;
	}
	void sub(int c)
	{
		tot--;
		cntSiz[cnt[c]]--;
		if (cnt[c] == maxCnt && cntSiz[cnt[c]] == 0)
			maxCnt--;
		cnt[c]--;
		cntSiz[cnt[c]]++;
	}
};
vector<int> colset[N];
Color subtree, rest;
bool vis2[N];

void increase(int x, int f, bool changeRest = false)
{
	for (auto c : colset[x])
	{
		subtree.add(c);
		if (changeRest)
			rest.sub(c);
	}
	for (auto [y, id] : newG[x])
		if (y != f)
			increase(y, x, changeRest);
}
void decrease(int x, int f, bool changeRest = false)
{
	for (auto c : colset[x])
	{
		subtree.sub(c);
		if (changeRest)
			rest.add(c);
	}
	for (auto [y, id] : newG[x])
		if (y != f)
			decrease(y, x, changeRest);
}
int ans[N];
int originMax;
void dfs1(int x, int f, int id, bool keep)
{
	vis2[x] = 1;
	int hsonID = 0;
	for (auto [y, newID] : newG[x])
	{
		if (y == hson[x])
			hsonID = newID;
		if (y == f || y == hson[x])
			continue;
		dfs1(y, x, newID, false);
	}
	if (hson[x])
		dfs1(hson[x], x, hsonID, true);
	for (auto c : colset[x])
	{
		subtree.add(c);
		rest.sub(c);
	}
	for (auto [y, id] : newG[x])
		if (y != f && y != hson[x])
			increase(y, x, true);
	ans[id] = rest.maxCnt + subtree.maxCnt - originMax;
	if (!keep)
		decrease(x, f, true);
}
void init(int n, int m)
{
	top = cnt = 0;
	assassass = 0;
	for (int i = 1; i <= n; i++)
	{
		G[i].clear();
		newG[i].clear();
	}
	for (int i = 1; i <= n; i++)
	{
		dfn[i] = low[i] = 0;
		sccID[i] = 0;
		hson[i] = 0;
		siz[i] = 0;
		vis2[i] = 0;
		colset[i].clear();
	}
	for (int i = 1; i <= m; i++)
		ans[i] = 0;
}
int a[N];
void work()
{
	int n, m;
	cin >> n >> m;
	init(n, m);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		if (x == y)
			continue;
		G[x].push_back({y, i});
		G[y].push_back({x, i});
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i, 0, 0);
	{
		set<pii> s;
		vector<int> vis(cnt + 1);
		for (int i = 1; i <= n; i++)
		{
			int x = sccID[i];
			for (auto [j, id] : G[i])
			{
				int y = sccID[j];
				if (x == y)
					continue;
				if (s.find({x, y}) == s.end())
				{
					newG[x].push_back({y, id});
					s.insert({x, y});
				}
			}
		}
		for (int i = 1; i <= n; i++)
			colset[sccID[i]].push_back(a[i]);
	}
	{
		int totans = 0;
		for (int i = 1; i <= cnt; i++)
			if (vis2[i] == false)
			{
				increase(i, 0);
				swap(subtree, rest);
				totans += rest.maxCnt;
				originMax = rest.maxCnt;
				dfs0(i, 0);
				dfs1(i, 0, 0, 0);
				swap(subtree, rest);
				decrease(i, 0);
			}
		for (int i = 1; i <= m; i++)
			ans[i] += totans;
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << " \n"[i == m];
}
int main()
{

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while (t-- > 0)
	{
		work();
	}
}