#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define save savee
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, a[N], m;

int answer[N];
vector<int> Adj[N], Adj2[N];

map<ii, int> mp;

//int answer[N];

int cnt;
int num[N], low[N];

int total, save;

int maxi1 = 0;
int cur1[N], cnt1[N];

// actually the complement of maxi1/cur1/cnt1

int maxi2 = 0;
int cur2[N], cnt2[N];

bool ck[N];

int sz[N], par[N];

void ins(int x){
	cnt1[cur1[x]]--;
	cur1[x]++;
	cnt1[cur1[x]]++;
	if(cur1[x] > maxi1) maxi1++;
	cnt2[cur2[x]]--;
	cur2[x]--;
	cnt2[cur2[x]]++;
	if(!cnt2[maxi2]) maxi2--;
}

void era(int x){
	cnt2[cur2[x]]--;
	cur2[x]++;
	cnt2[cur2[x]]++;
	if(cur2[x] > maxi2) maxi2++;
	cnt1[cur1[x]]--;
	cur1[x]--;
	cnt1[cur1[x]]++;
	if(!cnt1[maxi1]) maxi1--;
}

vector<int> nodes;

void dfs1(int u, int p){
	nodes.pb(u);
	cnt++;
	num[u] = low[u] = cnt;
	for(auto v : Adj[u]){
		if(!num[v]){
			Adj2[u].pb(v);
			par[v] = u;
			//cout << u << " " << v << "\n";
			dfs1(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] > num[u]){
				//cout << "OK " <<  u << " " << v << "\n";
				if(mp[{u, v}] > 0) ck[mp[{u, v}]] = 1;
			}
		}
		else if(v != p){
			low[u] = min(low[u], num[v]);
		}
	}
}

vector<int> get_nodes;

void prep(int u){
	sz[u] = 1;
	for(auto v : Adj2[u]){
		prep(v);
		sz[u] += sz[v];
	}
}

void dfs3(int u){
	get_nodes.pb(u);
	for(auto v : Adj2[u]) dfs3(v);
}


void dfs2(int u, bool er){
	//sz[u] = 1;
	ii maxi = {-1, -1};
	for(auto v : Adj2[u]){
		//dfs2(v);
	//	sz[u] += sz[v];
		maxi = max(maxi, {sz[v], v});
	}
	if(maxi.fi >= 0){
		for(auto v : Adj2[u]){
			if(v != maxi.se) dfs2(v, 1);
		}
		dfs2(maxi.se, 0);
		get_nodes.clear();
		for(auto v : Adj2[u]) if(v != maxi.se) dfs3(v);
		for(auto it : get_nodes) ins(a[it]);
	}
	ins(a[u]);
	//cout << u << " " <<par[u] << " "<< mp[{u, par[u]}] << " " <<  maxi1 << " " << maxi2 << " " << save << "\n";
	if(mp[{u, par[u]}] >= 0) answer[mp[{u, par[u]}]] = maxi1 + maxi2 - save;
	if(er){
		get_nodes.clear();
		dfs3(u);
		for(auto it : get_nodes) era(a[it]);
	}
}

void init(){
	for(int i = 1; i <= n; i++){
		Adj[i].clear(), Adj2[i].clear();
		mp.clear();
		cnt = 0;
		get_nodes.clear();
		par[i] = 0; sz[i] = 0;
		num[i] = low[i] = 0;
	}
	for(int i = 1; i <= m; i++) ck[i] = answer[i] = 0;
	total = 0;
}

#ifdef local
void process(){
	cin >> n >> m;
	init();
	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;
		if(x > y) swap(x, y);
		if(mp.find({x, y}) != mp.end()) mp[{x, y}] = -1;
		else{
			mp[{x, y}] = mp[{y, x}] = i;
			Adj[x].pb(y), Adj[y].pb(x);
		}
	}
	for(int i = 1; i <= n; i++){
		if(num[i]) continue;
		nodes.clear();
		dfs1(i, i);
		cnt2[0] = 1e5;
		for(auto it : nodes){
			cnt2[cur2[a[it]]]--;
			cur2[a[it]]++;
			cnt2[cur2[a[it]]]++;
			if(cur2[a[it]] > maxi2) maxi2++;
		}
		//cout << maxi2 << "\n";
		save = maxi2;
		total += save;
		//continue;
		prep(i);
		//continue;
		dfs2(i, 0);
		for(auto it : nodes){
			maxi1 = maxi2 = 0;
			cur1[a[it]] = cur2[a[it]] = 0;
		}
		for(int j = 0; j <= nodes.size(); j++) cnt1[j] = cnt2[j] = 0;
	}
	for(int i = 1; i <= m; i++){
		if(!ck[i]) answer[i] = 0;
		//cout << ck[i] << "\n";
		cout << total + answer[i];
                if(i != m) cout << " ";
	}
	cout << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("kek.inp", "r", stdin);
	//freopen("kek.out", "w", stdout);
	int t;
	cin >> t;
	while(t--) process();
}
#endif