#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#define N 100000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
struct reads
{
    int l,r;
    bool operator < (const reads &t)const
    {
	return l<t.l;    
    }
};
reads tongs[N+1];
struct rds
{
    int num,data;
};
vector<rds>E[N+1];
vector<int>ES[N+1];
vector<int>ET[N+1];
int T,n,m,rst,res,lengths,lg[N+1],a[N+1],X[N+1],Y[N+1],cl[N+1],depth[N+1],fa[N+1][21],cater,leng,lengs,tong[N+1],length,dque[N+1],top,dfn[N+1],low[N+1],dfns[N+1],sz[N+1],belong[N+1],q[N+1],cnt[N+1],A[N+1],B[N+1],ST[N+1][21],ans[N+1];
bool used[N+1];
stack<int>p;
void add(int x,int y,int z)
{
    E[x].push_back((rds){y,z}),E[y].push_back((rds){x,z});
    return;
}
void add2(int x,int y)
{
    ES[x].push_back(y),ES[y].push_back(x);
    return;
}
void tarjan(int x,int y)
{
    dfn[x]=low[x]=++leng,p.push(x);
    for (int i=0;i<E[x].size();++i)
    {
	if (!dfn[E[x][i].num])
	{
	    tarjan(E[x][i].num,E[x][i].data),low[x]=min(low[x],low[E[x][i].num]);
	    if (low[E[x][i].num]>dfn[x])
	    {
	        ++cater;
		while (p.top()!=E[x][i].num) belong[p.top()]=cater,p.pop();
		belong[p.top()]=cater,p.pop();
	    }
	}
	else if (E[x][i].data!=y) low[x]=min(low[x],dfn[E[x][i].num]);
    }
    return;
}
void dfs(int x)
{
    used[x]=1,dfns[x]=++lengs,sz[x]=1;
    for (int i=0;i<ES[x].size();++i)
	if (!used[ES[x][i]])
	    cl[ES[x][i]]=cl[x],depth[ES[x][i]]=depth[x]+1,fa[ES[x][i]][0]=x,dfs(ES[x][i]),sz[x]+=sz[ES[x][i]];
    return;
}
bool cmp(int x,int y)
{
    return a[x]<a[y];
}
bool cmp2(int x,int y)
{
    return dfns[x]<dfns[y];
}
bool LENG(int x,int y)
{
    if (!x) return 1;
    return dfns[x]<=dfns[y]&&dfns[y]<=dfns[x]+sz[x]-1;
}
int lca(int x,int y)
{
    if (depth[x]<depth[y]) swap(x,y);
    for (int i=lg[cater];i>=0;--i)
	if (depth[fa[x][i]]>=depth[y])
	    x=fa[x][i];
    if (x==y) return x;
    for (int i=lg[cater];i>=0;--i)
	if (fa[x][i]!=fa[y][i])
	    x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int tfa(int x,int y)
{
    for (int i=lg[cater];i>=0;--i)
	if (depth[fa[x][i]]>depth[y])
	    x=fa[x][i];
    return x;
}
void dfs2(int x)
{
    for (int i=0;i<ET[x].size();++i) dfs2(ET[x][i]),cnt[x]+=cnt[ET[x][i]];
    A[x]=max(A[x],cnt[x]);
    return;
}
void solve(int l,int r,int d)
{
    if (l>r) return;
    int lw=lg[r-l+1];
    ST[l][lw]=max(ST[l][lw],d),ST[r-(1<<lw)+1][lw]=max(ST[r-(1<<lw)+1][lw],d);
    return;
}
void dfs3(int x,int d)
{
    for (int i=0;i<ET[x].size();++i)
    {
	if (!x) dfs3(ET[x][i],cnt[ET[x][i]]);
	else B[tfa(ET[x][i],x)]=max(B[tfa(ET[x][i],x)],d-cnt[ET[x][i]]),dfs3(ET[x][i],d);
    }
    if (x)
    {
	lengths=0;
	for (int i=0;i<ET[x].size();++i) tongs[++lengths]=(reads){dfns[tfa(ET[x][i],x)],dfns[tfa(ET[x][i],x)]+sz[tfa(ET[x][i],x)]-1};
	sort(tongs+1,tongs+lengths+1);
        if (!lengths) solve(dfns[x]+1,dfns[x]+sz[x]-1,d);
	else
	{
	    solve(dfns[x]+1,tongs[1].l-1,d);
	    for (int i=2;i<=lengths;++i) solve(tongs[i-1].r+1,tongs[i].l-1,d);
	    solve(tongs[lengths].r+1,dfns[x]+sz[x]-1,d);
	}
    }
    return;
}
void dfs4(int x)
{
    used[x]=1,B[x]=max(B[x],ST[dfns[x]][0]);
    for (int i=0;i<ES[x].size();++i)
	if (!used[ES[x][i]])
	    B[ES[x][i]]=max(B[ES[x][i]],B[x]),dfs4(ES[x][i]),A[x]=max(A[x],A[ES[x][i]]);
    return;
}
int main()
{
    int ps,d,ds;
    for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
    T=read();
    while (T--)
    {
	n=read(),m=read(),cater=leng=lengs=res=0,ps=1;
	for (int i=1;i<=n;++i) a[i]=read(),dfn[i]=used[i]=fa[i][0]=A[i]=B[i]=0,E[i].clear(),ES[i].clear(),q[i]=i;
	for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),add(X[i],Y[i],i);
	for (int i=1;i<=n;++i)
	    if (!dfn[i])
	    {
		tarjan(i,0),++cater;
		while (p.top()!=i) belong[p.top()]=cater,p.pop();
		belong[p.top()]=cater,p.pop();
	    }
	for (int i=1;i<=m;++i)
	    if (belong[X[i]]!=belong[Y[i]])
		add2(belong[X[i]],belong[Y[i]]);
	for (int i=1;i<=cater;++i) used[i]=0;
	depth[1]=1;
	for (int i=1;i<=cater;++i)
	    if (!used[i])
		cl[i]=i,dfs(i);
	for (int i=1;i<=lg[cater];++i)
	    for (int j=1;j<=cater;++j)
		fa[j][i]=fa[fa[j][i-1]][i-1];
	for (int i=0;i<=lg[cater];++i)
	    for (int j=1;j+(1<<i)-1<=cater;++j)
		ST[j][i]=0;
	sort(q+1,q+n+1,cmp);
	for (int i=1;i<=n;++i)
	    if (i==n||a[q[i]]!=a[q[i+1]])
	    {
		length=top=0;
		for (int j=ps;j<=i;++j) tong[++length]=belong[q[j]],ET[belong[q[j]]].clear(),cnt[belong[q[j]]]=0;
		sort(tong+1,tong+length+1,cmp2),length=unique(tong+1,tong+length+1)-tong-1;
		for (int j=1;j<=length;++j)
		{
		    d=0;
		    while (top&&!LENG(dque[top],tong[j]))
		    {
			if (d) ET[dque[top]].push_back(d);
			d=dque[top],top--;
		    }
		    if (d)
		    {
			ds=lca(d,tong[j]);
			if (!top||ds!=dque[top]) ET[ds].clear(),ET[ds].push_back(d),cnt[ds]=0,dque[++top]=ds;
			else ET[dque[top]].push_back(d);
		    }
		    dque[++top]=tong[j];
		}
		for (int j=2;j<=top;++j) ET[dque[j-1]].push_back(dque[j]);
		for (int j=ps;j<=i;++j) cnt[belong[q[j]]]++;
		rst=i-ps+1,dfs2(dque[1]),dfs3(dque[1],dque[1]?cnt[dque[1]]:0),ps=i+1;
	    }
	for (int i=lg[cater];i>=1;--i)
	    for (int j=1;j+(1<<i)-1<=cater;++j)
		ST[j][i-1]=max(ST[j][i-1],ST[j][i]),ST[j+(1<<(i-1))][i-1]=max(ST[j+(1<<(i-1))][i-1],ST[j][i]);
	for (int i=1;i<=cater;++i) used[i]=0;
	for (int i=1;i<=cater;++i)
	    if (!used[i])
		dfs4(i),res+=A[i];
	for (int i=1;i<=m;++i)
	{
	    if (belong[X[i]]==belong[Y[i]]) ans[i]=res;
	    else
	    {
		if (depth[belong[X[i]]]>depth[belong[Y[i]]]) swap(X[i],Y[i]);
		ans[i]=res+A[belong[Y[i]]]+B[belong[Y[i]]]-A[cl[belong[Y[i]]]];
	    }
	}
        for (int i=1;i<=m-1;++i) printf("%d ",ans[i]);
	printf("%d\n",ans[m]);
    }
    return 0;
}