#include<bits/stdc++.h>
#define gt getchar
#define pt putchar
#define fst first
#define scd second
typedef long long ll;
using namespace std;
const int N=5e5+10;
typedef pair<int,int> pii;
inline bool __(char ch){return ch>=48&&ch<=57;}
template<class T> inline void read(T &x){
	x=0;bool sgn=0;char ch=gt();
	while(!__(ch)&&ch!=EOF) sgn|=(ch=='-'),ch=gt();
	while(__(ch)) x=(x<<1)+(x<<3)+(ch&15),ch=gt();
	if(sgn) x=-x;
}
template<class T,class ...T1> inline void read(T &x,T1 &...x1){
	read(x);
	read(x1...);
}
template<class T> inline void print(T x){
	static char st[70];short top=0;
	if(x<0) pt('-');
 	do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
    while(top) pt(st[top--]);
}
template<class T> inline void printsp(T x){
	print(x);
	putchar(' ');
}
template<class T> inline void println(T x){
	print(x);
	putchar('\n');
}
int n,m,a[N],u[N],v[N];
int dccCnt,id[N];
vector<int>dcc[N];
vector<int>V[N];
int low[N],dfn[N],cnt,head[N],cnt1=1,vis[N];
bool is_cut[N<<1];
int g[N],f[N],mx,g1[N],f1[N],mx1;
int L[N],R[N],tot,nd[N],big[N],sz[N];
map<pair<int,int>,int>M1;
ll ans=0,ans1[N],out[N];
struct node{
	int nxt,to;
}e[N];
map<pair<int,int>,int> M;
void add_edge(int x,int y){
	e[++cnt1].to=y;
	e[cnt1].nxt=head[x];
	head[x]=cnt1;
	//cout<<cnt1<<endl;
	//cout<<e[cnt1].to<<endl;
} 
void tarjan(int u,int edge){
	dfn[u]=low[u]=++cnt;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){ 
			tarjan(v,i);
			low[u]=min(low[u],low[v]); 
			if(low[v]>dfn[u]){
				is_cut[i]=1;
				is_cut[i^1]=1;
			}
		}
		else if(i!=(edge^1))low[u]=min(low[u],dfn[v]);
	}
}
void add_double(int x,int y){
	V[x].push_back(y);
}
void dfs(int u){
	dcc[dccCnt].push_back(a[u]);
	id[u]=dccCnt;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(id[v]!=0||is_cut[i])continue;
		dfs(v); 
	}
}
void add(int k){
	for(auto x:dcc[k]){
		g[f[x]]--;
		f[x]++;
		g[f[x]]++;
		mx=max(mx,f[x]);
	}
}
void del(int k){
	for(auto x:dcc[k]){
		g[f[x]]--;
		f[x]--;
		g[f[x]]++;
		mx=(g[mx]>0?mx:mx-1);
	}
}
void add1(int k){
	for(auto x:dcc[k]){
		g1[f1[x]]--;
		f1[x]++;
		g1[f1[x]]++;
		mx1=max(mx1,f1[x]);
	}
}
void del1(int k){
	for(auto x:dcc[k]){
		g1[f1[x]]--;
		f1[x]--;
		g1[f1[x]]++;
		mx1=(g1[mx1]>0?mx1:mx1-1);
	}
}
void _dfs(int u,int fa){
	vis[u]=1;
	add(u);
	//cout<<u<<endl;
	for(auto t:V[u]){
		if(t!=fa)_dfs(t,u);
	}
}
void _dfs1(int u,int fa){
	del(u);
	for(auto t:V[u]){
		if(t!=fa)_dfs1(t,u);
	}
}
int getans(){return mx+mx1;}
void dfs0(int u,int fa){
	L[u]=++tot;
	nd[tot]=u;
	sz[u]=dcc[u].size();
	for(auto v:V[u]){
		if(v!=fa){
			dfs0(v,u);
			sz[u]+=sz[v];
			if(!big[u]||sz[big[u]]<sz[v])big[u]=v;
		}
	}
	R[u]=tot;
}
void dfs1(int u,int fa,bool keep){
	for(int v:V[u]){
		if(v!=fa&&v!=big[u]){
			dfs1(v,u,0);
		}
	}
	if(big[u]){
		dfs1(big[u],u,1);
	}
	for(int v:V[u]){
		if(v!=fa&&v!=big[u]){
			for(int i=L[v];i<=R[v];i++) {
       	 		del(nd[i]);
       	 		add1(nd[i]);
     		}
		}
	}
	del(u);
	add1(u);
	M1[make_pair(u,fa)]=ans+getans();
	if(keep==false){
    	for(int i=L[u];i<=R[u];i++) {
     		add(nd[i]);
     		del1(nd[i]);
    	}
  	}
}
void clean(){
	M.clear(),M1.clear();
	tot=0;dccCnt=0;cnt1=1;ans=0;
	for(int i=0;i<=n;i++)big[i]=0,id[i]=0;
	for(int i=0;i<=m;i++)ans1[i]=0,out[i]=0;
	for(int i=0;i<=n;i++)dcc[i].clear(),V[i].clear();
	for(int i=0;i<=2*m+1;i++)is_cut[i]=0,e[i].nxt=0,e[i].to=0;
	for(int i=0;i<=m;i++)u[i]=v[i]=0;
	for(int i=0;i<=n;i++){
		L[i]=0,R[i]=0,nd[i]=0,big[i]=0,sz[i]=0;
		low[i]=0;
		dfn[i]=0;
		cnt=0;
		head[i]=0;
		vis[i]=0;
		g[i]=0,f[i]=0,mx=0,g1[i]=0,f1[i]=0,mx1=0;
	}
}
void solve(){
	clean();
	read(n,m);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	for(int i=1;i<=m;i++){
		read(u[i],v[i]);
		add_edge(u[i],v[i]);
		add_edge(v[i],u[i]);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
	for(int i=1;i<=n;i++){
		if(!id[i]){
			dccCnt++;
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=e[j].nxt){
			int to=e[j].to;
			if(id[i]!=id[to]){
				add_double(id[i],id[to]);
			}
		}
	}
//	for(int i=1;i<=m*2;i++)cout<<is_cut[i]<<endl;
	int tt=n;
	n=dccCnt;
	//cout<<n<<endl;
//	for(int i=1;i<=n;i++){for(auto j:dcc[i])printf("%d ",j);puts("");}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		_dfs(i,0);
		ans+=mx;
		ans1[i]=mx;
		_dfs1(i,0);
	}
	for(int i=1;i<=m;i++){
		if(!is_cut[i*2])out[i]=ans;
	}
	for(int i=1;i<=n;i++)vis[i]=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		_dfs(i,0);
		ans-=ans1[i];
		dfs0(i,0);
		dfs1(i,0,0);
		ans+=ans1[i]; 
		_dfs1(i,0);
	}
	for(int i=1;i<=m;i++){
		if(!out[i]){
			out[i]=max(
			M1[make_pair(id[u[i]],id[v[i]])],
			M1[make_pair(id[v[i]],id[u[i]])]);
		}
	}
	for(int i=1;i<=m;i++){
		if(!(i^m))cout<<out[i];
		else cout<<out[i]<<" ";
	}
	cout<<endl;
	n=tt;
	return;
}
int main(){
	int T;read(T);
	while(T--)solve();
	return 0;
}
/*
1
3 3
1 2 3
1 2
1 3
2 3
*/