#include<bits/stdc++.h>
using namespace std;

const int N=1e5+100;
int b[N];

struct edge{
    int x,y,c,next;
}a[2*N];int len,last[N];

void ins(int x,int y,int c){
    a[++len].x=x;a[len].y=y;a[len].c=c;
    a[len].next=last[x];last[x]=len;
}

int dfn[N],low[N],sum,sta[N],tot,ID[N],cnt;bool bk[N];
vector<int> B[N];

void dfs(int x,int las){
    bk[x]=false;dfn[x]=low[x]=++sum;
    sta[++tot]=x;
    for(int k=last[x];k;k=a[k].next){
        int y=a[k].y;
        if(bk[y]){
            dfs(y,a[k].c);
            low[x]=min(low[x],low[y]);
        }
        else if(a[k].c!=las) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        cnt++;
        while(true){
            ID[sta[tot]]=cnt;
            B[cnt].push_back(b[sta[tot]]);
            if(sta[tot]==x) break;
            tot--;
        }
        tot--;
    }
}

int L[N],R[N],sum2,now;
const int maxn=1e5;

struct tree{
    int lc,rc,c1,c2;
}tr[N*40];int Len;
int Root[N],ROOT[N],Ans[N];

void Add(int &now,int L,int R,int k,int c){
    if(!now) now=++Len;
    if(L==R) {tr[now].c1+=c;return ;}
    int mid=(L+R)>>1;
    int &lc=tr[now].lc,&rc=tr[now].rc;
    if(k<=mid) Add(lc,L,mid,k,c);
    else Add(rc,mid+1,R,k,c);
    tr[now].c1=max(tr[lc].c1,tr[rc].c1);
}

void pushup(int now,int NOW){
    int lc=tr[now].lc,rc=tr[now].rc;
    tr[now].c1=max(tr[lc].c1,tr[rc].c1);
    tr[now].c2=max(lc?tr[lc].c2:tr[tr[NOW].lc].c1,rc?tr[rc].c2:tr[tr[NOW].rc].c1);
}

void Change(int &now,int NOW,int L,int R,int k,int c){
    if(!now) now=++Len;
    if(L==R){
        tr[now].c1+=c;
        tr[now].c2=tr[NOW].c1-tr[now].c1;
        return ;
    }
    int mid=(L+R)>>1;
    int &lc=tr[now].lc,&rc=tr[now].rc;
    if(k<=mid) Change(lc,tr[NOW].lc,L,mid,k,c);
    else Change(rc,tr[NOW].rc,mid+1,R,k,c);
    pushup(now,NOW);
}

void merge(int &now1,int now2,int NOW,int L,int R){
    if(!now2) return ;
    if(!now1) {now1=now2;return ;}
    if(L==R){
        tr[now1].c1+=tr[now2].c1;
        tr[now1].c2=tr[NOW].c1-tr[now1].c1;
        return ;
    }
    int mid=(L+R)>>1;
    merge(tr[now1].lc,tr[now2].lc,tr[NOW].lc,L,mid);
    merge(tr[now1].rc,tr[now2].rc,tr[NOW].rc,mid+1,R);
    pushup(now1,NOW);
}

void dfs2(int x,int las){
    bk[x]=false;
    for(auto z:B[x])
        Change(Root[x],ROOT[now],1,maxn,z,1);
    for(int k=last[x];k;k=a[k].next){
        int y=a[k].y;
        if(bk[y]){
            dfs2(y,a[k].c);
            merge(Root[x],Root[y],ROOT[now],1,maxn);
        }
    }
    // printf("%d %d %d\n",x,tr[Root[x]].c1,tr[Root[x]].c2);
    Ans[las]=tr[Root[x]].c1+tr[Root[x]].c2-tr[ROOT[now]].c1;
}

int main()
{
    int T;
    scanf("%d",&T);

    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        len=0;for(int i=1;i<=n;i++) last[i]=0;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            ins(x,y,i);
            ins(y,x,i);
        }
        for(int i=1;i<=n;i++) bk[i]=true;

        sum=tot=cnt=0;
        sum2=0;
        for(int i=1;i<=n;i++)
            if(bk[i]){
                dfs(i,0);
                sum2++;
                L[sum2]=R[sum2-1]+1;
                R[sum2]=cnt;
            }

        int lim=len;
        len=0;for(int i=1;i<=n;i++) last[i]=0;
        for(int i=1;i<=lim;i++)
            if(ID[a[i].x]!=ID[a[i].y])
                ins(ID[a[i].x],ID[a[i].y],a[i].c);

        for(int i=1;i<=cnt;i++) Root[i]=0;

        int Sum=0;Len=0;
        for(int i=1;i<=m;i++) Ans[i]=0;
        for(int i=1;i<=n;i++) bk[i]=true;
        for(int i=1;i<=sum2;i++){
            ROOT[i]=0;
            for(int j=L[i];j<=R[i];j++)
                for(auto x:B[j])
                    Add(ROOT[i],1,maxn,x,1);
            now=i;
            Sum=Sum+tr[ROOT[i]].c1;
            dfs2(L[i],0);
        }

        for(int i=1;i<=m;i++) printf("%d ",Ans[i]+Sum);
        printf("\n");

        for(int i=1;i<=cnt;i++) B[i].clear();
        for(int i=1;i<=Len;i++)
            tr[i].lc=tr[i].rc=tr[i].c1=tr[i].c2=0;
    }

    return 0;
}