//蒟蒻一枚 rp++
//即得易见平凡，仿照上例显然。留作习题答案略，读者自证不难
//反之亦然同理，推论自然成立，略去过程Q.E.D.，由上可知证毕
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define re register
#define il inline
#define gc() getchar()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define tep(i,x) for(int i=head[x];~i;i=ne[i])
#define ls(x) x<<1
#define rs(x) x<<1|1
#define eps (1e-9)
#define inf 0x3f3f3f3f
#define INF 1e16
#define pii pair<int,int>
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define fi first
#define sc second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef double db;
namespace IO{
//	#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<9,stdin),p1==p2)?EOF:*p1++)
//	char buf[1<<9],*p1=buf,*p2=buf;
	template<typename T> inline void read(T &x){
		bool f=1;x=0;char ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
		while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=gc();
		x=f?x:-x;
	}
	template<typename T> inline void write(T x){
		if(x<0) putchar('-'),x=-x;
	   	if(x>9) write(x/10);
	   	putchar(char('0'+x%10));
	}
	template <typename T,typename ...Args> inline
	void read(T &x,Args &...args){read(x);read(args...);}
	template<typename T> inline void write(T x,char c){write(x),putchar(c);}
}
using namespace IO;
namespace MOD{
	typedef uint32_t u32;
	typedef uint64_t u64;
	typedef __uint128_t u128;
	u64 p,m;
	void set_mod(u32 mod){
		m=mod,p=-m/m+1;
	}
	u64 mo(u64 x){//取模优化
		x-=u64((u128)x*p>>64)*m;
		return (x>=m)?x-m:x;
	}
}
bool _ST;
const int N=5e5+100;
int n,m,a[N],ans[N],val[N];
int Ti,st[N],top,dfn[N],siz[N],son[N],low[N],col[N],cnt_dcc;
vector<pii> E[N],e[N];
vector<int> cc[N];
int num[N*2],cnt[N],mx,is[N];
bool vis[N];
void add(int x){
	--cnt[num[x]++];
	++cnt[num[x]];
	mx=max(mx,num[x]);
}
void del(int x){
	--cnt[num[x]--];
	++cnt[num[x]];
	if(!cnt[mx]) --mx;
}
void tarjan(int x,int ine){
	low[x]=dfn[x]=++Ti,st[++top]=x;
	add(a[x]);
	for(auto i:e[x]){
		int y=i.fi,id=i.sc;
		if(!dfn[y]){
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]){
				++cnt_dcc;
				int u;
				do{
					u=st[top--];
					col[u]=cnt_dcc; 
				}while(u!=y);
			}
		}
		else if(id!=ine) low[x]=min(low[x],dfn[y]);
	}
}
void dfs1(int x){
	del(a[x]),vis[x]=1;
	for(auto i:e[x]) if(!vis[i.fi]) dfs1(i.fi);
}
void dfs2(int x,int ff){
	siz[x]=cc[x].size(),son[x]=0,vis[x]=1;
	for(auto i:E[x]) if(i.fi!=ff){
		dfs2(i.fi,x);
		siz[x]+=siz[i.fi];
		if(siz[i.fi]>siz[son[x]]) son[x]=i.fi,is[x]=i.sc;
	}
}
int SON;
bool opt[N];
void calc(int x,int ff,int op){
	opt[x]^=1;
	if(op) for(auto c:cc[x]) add(a[c]);
	else   for(auto c:cc[x]) del(a[c]);
	for(auto i:E[x]) if(i.fi!=ff&&i.fi!=SON) calc(i.fi,x,op);
}
void dfs3(int x,int ff){
	for(auto i:E[x]) {
		if(i.fi!=ff&&i.fi!=son[x]) {
			dfs3(i.fi,x),ans[i.sc]+=mx;
			calc(i.fi,x,0);
		}
	}
	if(son[x]){
		dfs3(son[x],x),ans[is[x]]+=mx;
		SON=son[x];
	}
	calc(x,ff,1),SON=0;
}
void dfs4(int x,int ff){//子树补信息 
	SON=son[x],calc(x,ff,1),SON=0;
	
	if(son[x]){
		ans[is[x]]+=mx;
//		cerr<<"! "<<son[x]<<": ";rep(j,1,n) cerr<<num[j]<<" ";cerr<<endl;
		dfs4(son[x],x);
	}
	for(auto i:E[x]) if(i.fi!=ff&&i.fi!=son[x]){
		SON=0,calc(i.fi,x,0),ans[i.sc]+=mx;
//		cerr<<"! "<<i.fi<<": ";rep(j,1,n) cerr<<num[j]<<" ";cerr<<endl;
		dfs4(i.fi,x);
//		SON=0,calc(i.fi,x,1);
//		cerr<<"? "<<x<<": ";rep(j,1,n) cerr<<num[j]<<" ";cerr<<endl;
	}
	SON=0;
}
void solve(){
	read(n,m);Ti=cnt_dcc=0,cnt[0]=n;
	rep(i,1,n)read(a[i]);
	rep(i,1,m){
		int u,v;read(u,v);
		e[u].pb({v,i}),e[v].pb({u,i});
	}
	int al=0;
	rep(i,1,n){
		if(!dfn[i]){
			int las=cnt_dcc;
			tarjan(i,0);
			if(top){
				++cnt_dcc;
				int u;
				do{
					u=st[top--];
					col[u]=cnt_dcc; 
				}while(u!=i);
			}
			al+=mx;
			rep(j,las+1,cnt_dcc) val[j]=mx;
			dfs1(i);
		}
	}
	rep(x,1,n){
		cc[col[x]].pb(x);
		for(auto i:e[x]){
			int y=i.fi,id=i.sc;
			if(col[x]==col[y]) ans[id]=al;
			else{
				E[col[x]].pb({col[y],id});
				ans[id]=al-val[col[x]];
			}
		}
		e[x].clear(),vis[x]=0;
	}
//	rep(i,1,cnt_dcc){
//		cerr<<i<<": ";for(auto j:cc[i]) cerr<<j<<" ";cerr<<endl;
//	}
	rep(i,1,cnt_dcc){
		if(!vis[i]){
			dfs2(i,0);
			dfs3(i,0),calc(i,0,0);
			dfs4(i,0),calc(i,0,0);
			assert((mx==0));
//			rep(j,1,cnt_dcc) cerr<<opt[j]<<" ";cerr<<endl;
//			cerr<<mx<<endl;
		}
	}
	rep(i,1,m) write(ans[i]),putchar((i<m)?' ':'\n');
	rep(i,1,n) dfn[i]=low[i]=col[i]=val[i]=vis[i]=is[i]=cnt[i]=num[i]=0;
	rep(i,1,cnt_dcc) E[i].clear(),vis[i]=0,cc[i].clear();
}
bool _ED;
signed main(){
	fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
//	freopen("ex_exam2.in","r",stdin);
	//freopen(".out","w",stdout);
	int T=1;
	read(T);
	while(T--) solve();
	fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
	return 0;
}
//谨记:
//十年OI一场空，不开longlong见祖宗
//数据千万条，清空第一条。多测不清空，爆零两行泪。清空不规范，TLE总相伴。
//快读要加类型名
/*
1
3 3
1 2 3
1 2
1 3
2 3
*/