已知的情报：
https://qoj.ac/submission/360378
https://www.luogu.com.cn/record/151948058

#include<bits/stdc++.h>
using namespace std;
#define RSET(_$,$_) for(int _=1;_<=$_;++_) _$[_].clear()
constexpr int N=1e5+7;

int c[N],po[N],low[N],c1,c2;
basic_string<pair<int,int>> e[N],g[N];
basic_string<int> stk,cpo[N];
inline void tarjan(int x,int f){
	stk+=x;
	int dfn=low[x]=++c1;
	for(auto [i,_]:e[x]) if(_!=f){
		if(!low[i]) tarjan(i,_);
		low[x]<low[i]?: low[x]=low[i];
	}
	if(low[x]==dfn){
		++c2;
		do	cpo[c2]+=stk.back(),
			po[stk.back()]=c2,
			stk.pop_back();
		while(cpo[c2].back()!=x);
	}
}

map<int,int> M[N],P,_p,Q,_q;
int A[N],h[N],s[N],res[N];
bitset<N> vi;
inline void dfs1(int x,int f){
	int t=0;
	s[x]=1;
	for(auto [i,_]:g[x]) if(i!=f){
		A[i]=_, dfs1(i,x);
		s[i]<t?: t=s[h[x]=i];
		s[x]+=s[i];
	}
}
inline void upd(int x){
	int t=0;
	for(auto [k,c]:M[x])
		--_p[t=P[k]], P[k]=t+c, ++_p[t+c];
	for(auto [k,c]:M[x])
		--_q[t=Q[k]], _q[t]?: _q.erase(t),
		Q[k]=t-c, ++_q[t-c];
}
inline void dfs2(int x,int f){
	for(auto [i,_]:g[x]) if(i!=f)
		dfs2(i,x);
	upd(x);
}
int la;
void dfs3(int x,int f,bool d=0){
	vi[x]=1;
	if(!h[x]) goto tag;
	for(auto [i,_]:g[x]) if(i!=f&&i!=h[x]) dfs3(i,x);
	dfs3(h[x],x,1);
	for(auto [i,_]:g[x]) if(i!=f&&i!=h[x]) dfs2(i,x);
	tag: upd(x);
	res[A[x]]=_p.rbegin()->first+
			  _q.rbegin()->first-la;
	if(!d){
		for(auto [k,c]:P) --_q[f=Q[k]], Q[k]=f+c, ++_q[f+c];
		P.clear(); _p.clear();
	}
}
inline void dfs4(int x,int f){
	for(auto [i,_]:g[x]) if(i!=f)
		dfs4(i,x);
	for(auto [k,c]:M[x])
		--_q[f=Q[k]], Q[k]=f+c, ++_q[f+c];
}

main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--){
	int n,m,tans=c1=c2=0;
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>c[i];
	for(int i=1,p,q;i<=m;++i) cin>>p>>q,
		e[p]+={q,i}, e[q]+={p,i};
	for(int i=1;i<=n;++i) 
		if(!low[i]) tarjan(i,0);
	for(int i=1;i<=c2;++i)
		for(int j:cpo[i])
			++M[i][c[j]];
	for(int i=1;i<=n;++i) for(auto [j,id]:e[i])
		if(po[i]!=po[j])
			g[po[i]]+={po[j],id};

	for(int i=1;i<=n;++i) 
		if(!s[i]) dfs1(i,0);
	for(int i=1;i<=c2;++i) if(!vi[i]){
		P.clear(), _p.clear();
		Q.clear(), _q.clear();
		dfs4(i,0);
		tans+=la=_q.rbegin()->first;
		dfs3(i,0,1);
	}
	for(int i=1;i<=m;++i)
		cout<<res[i]+tans<<" \n"[i==m];

RSET(e,n); RSET(g,c2); RSET(cpo,c2); RSET(M,c2);
vi.reset();
bzero(h+1,4*c2);
bzero(s+1,4*c2);
bzero(res+1,4*m);
bzero(low+1,4*n);
}
}