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

using namespace std;

const int N = 2e5 + 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;
struct Edges
{
	struct Edge
	{
		int to, nxt, id;
	};
	vector<int> head;
	vector<Edge> e;
	Edges() {}
	Edges(int n)
	{
		head.resize(n + 1);
		e.clear();
		e.push_back(Edge());
	}
	void addSingle(int x, int y, int id)
	{

		e.push_back(Edge{y, head[x], id});
		head[x] = e.size() - 1;
	}
	void add(int x, int y, int id)
	{
		addSingle(x, y, id);
		addSingle(y, x, id);
	}
};
void work()
{
	cin >> n >> m;
	vector<int> a(n + 1), head(n + 1);
	Edges G(n), newG(n);
	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)
			G.add(x, y, i);
	}
	vector<int> dfn(n + 1), low(n + 1), col(n + 1), stk;
	int dfncnt = 0, scccnt = 0;
	vector<vector<int>> newa(n + 1);
	auto tarjan = [&](auto &tarjan, int x, int fromID) -> void
	{
		stk.push_back(x);
		dfn[x] = low[x] = ++dfncnt;
		for (int i = G.head[x]; i; i = G.e[i].nxt)
		{
			if (G.e[i].id == fromID)
				continue;
			int y = G.e[i].to;
			if (!dfn[y])
			{
				tarjan(tarjan, y, G.e[i].id);
				low[x] = min(low[x], low[y]);
			}
			else
				low[x] = min(low[x], dfn[y]);
		}
		if (dfn[x] == low[x])
		{
			scccnt++;
			int now = 0;
			do
			{
				now = stk.back();
				col[now] = scccnt;
				newa[scccnt].push_back(a[now]);
				stk.pop_back();
			} while (now != x);
		}
	};
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
		{

			tarjan(tarjan, i, 0);
		}
	for (int x = 1; x <= n; x++)
	{
		for (int i = G.head[x]; i; i = G.e[i].nxt)
		{
			int y = G.e[i].to;
			if (col[x] == col[y])
				continue;
			newG.addSingle(col[x], col[y], G.e[i].id);
		}
	}
	vector<int> siz(scccnt + 1), hson(scccnt + 1);
	auto dfs0 = [&](auto &dfs0, int x, int f) -> void
	{
		siz[x] = 1;
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f)
				continue;
			dfs0(dfs0, y, x);
			if (siz[hson[x]] < siz[y])
				hson[x] = y;
			siz[x] += siz[y];
		}
	};
	for (int i = 1; i <= scccnt; i++)
		if (siz[i] == 0)
			dfs0(dfs0, i, 0);
	vector<int> ans(m + 1), vis(scccnt + 1);
	struct State
	{
		unordered_map<int, int> cnt, cntcnt;
		int maxcnt = 0;
		void addone(int x)
		{
			if (cnt[x])
				cntcnt[cnt[x]]--;
			cnt[x]++;
			cntcnt[cnt[x]]++;
			if (cnt[x] > maxcnt)
				maxcnt = cnt[x];
		}
		void subone(int x)
		{
			cntcnt[cnt[x]]--;
			if (cnt[x] == maxcnt && cntcnt[x] == 0)
				maxcnt--;
			cnt[x]--;
			cntcnt[cnt[x]]++;
		}
	};
	State all;
	for (int i = 1; i <= n; i++)
		all.addone(a[i]);
	for (int i = 1; i <= m; i++)
		ans[i] = all.maxcnt;
	State up, down;
	auto changeSubtree = [&](auto &changeSubtree, int x, bool increase, int f) -> void
	{
		if (increase)
		{
			for (auto v : newa[x])
			{
				up.subone(v);
				down.addone(v);
			}
		}
		else
		{
			for (auto v : newa[x])
			{
				down.subone(v);
				up.addone(v);
			}
		}
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f)
				continue;
			changeSubtree(changeSubtree, y, increase, x);
		}
	};
	int subtreeAns = 0;
	auto dfs = [&](auto &dfs, int x, int fromID, int f, bool keep) -> void
	{
		int hsonID = -1;
		vis[x] = 1;
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f)
				continue;
			if (y == hson[x])
			{
				hsonID = newG.e[i].id;
				break;
			}
			dfs(dfs, y, newG.e[i].id, x, false);
		}
		if (hson[x])
			dfs(dfs, hson[x], hsonID, x, true);
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f || y == hson[x])
				continue;
			changeSubtree(changeSubtree, y, 1, x);
		}
		for (auto v : newa[x])
		{
			up.subone(v);
			down.addone(v);
		}
		if (fromID)
			ans[fromID] = ans[fromID] - subtreeAns + up.maxcnt + down.maxcnt;
		if (!keep)
			changeSubtree(changeSubtree, x, 0, f);
	};
	for (int i = 1; i <= scccnt; i++)
	{
		if (!vis[i])
		{
			auto addon = [&](auto &addon, int x, int f) -> void
			{
				for (auto v : newa[x])
					up.addone(v);
				for (int i = newG.head[x]; i; i = newG.e[i].nxt)
					if (newG.e[i].to != f)
						addon(addon, newG.e[i].to, x);
			};
			addon(addon, i, 0);
			subtreeAns = up.maxcnt;
			dfs(dfs, i, 0, 0, 0);
		}
	}
	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;
	cin >> t;
	while (t-- > 0)
	{
		work();
	}
}