#include<bits/stdc++.h>
using namespace std;
const int N =1.1e5;
vector<pair<int,int> >E[N],e[N];
int col[N],bel[N];
int dfn[N],sk[N],low[N];
vector<int>a[N];
int ip=0,top=0,tot;
void dfs(int u,int ID){
    dfn[u]=low[u]=++ip;
    sk[++top]=u;
    for(auto [v,id]:E[u]){
        if(id==ID)continue;
        if(dfn[v]==0)dfs(v,id),low[u]=min(low[u],low[v]);
        else low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++tot;
        while(sk[top+1]!=u){
            bel[sk[top]]=tot;
            top--;
        }
    }
}



bool vis[N];
struct DATA
{
    int CNT[N],ton[N],MX;
    void ADD(int col){
        ton[CNT[col]]--;
        ++CNT[col];
        ton[CNT[col]]++;
        MX=max(MX,CNT[col]);
    }
    void DEL(int c){
        ton[CNT[c]]--;
        CNT[c]--;
        ton[CNT[c]]++;
        if(ton[MX]==0)MX--;
    }
    void add(int u,int fa){
        for(int x:a[u])ADD(x);
        for(auto [v,id]:e[u])if(v!=fa){
            add(v,u);
        }
    }
    void del(int u,int fa){
        for(int x:a[u])DEL(x);
        for(auto [v,id]:e[u])if(v!=fa){
            del(v,u);
        }
    }
}A,B;
int siz[N];
int ans[N];
int MX;
vector<int>now;

void init(int u,int fa){
    vis[u]=1;
    siz[u]=a[u].size();
    for(auto [v,id]:e[u])if(v!=fa)init(v,u),siz[u]+=siz[v];
}
void clear(){
    for(int x:now){
        B.DEL(x);
        A.ADD(x);
    }
    now.clear();
}
void push(int u,int fa){
    for(int x:a[u])now.push_back(x);
    for(auto [v,id]:e[u])if(v!=fa)push(v,u);
}
void DFS(int u,int fa){
    int son=0,ID;
    for(auto [v,id]:e[u])if(v!=fa)if(siz[v]>siz[son])son=v,ID=id;
    for(auto [v,id]:e[u])if(v!=son&&v!=fa){
        DFS(v,u);
        ans[id]=A.MX+B.MX-MX;
        clear();
    }
    if(son){DFS(son,u);
        ans[ID]=A.MX+B.MX-MX;
    }
    for(auto [v,id]:e[u])if(v!=son&&v!=fa)A.del(v,u),B.add(v,u),push(v,u);
    for(int x:a[u]){
        A.DEL(x);B.ADD(x);
        now.push_back(x);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>col[i];
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        // if(u==v)continue;
        E[u].push_back({v,i});
        E[v].push_back({u,i});
    }
    for(int i=1;i<=n;++i)if(dfn[i]==0)dfs(i,0);
    for(int u=1;u<=n;++u){
        for(auto [v,id]:E[u]){
            if(bel[u]!=bel[v])e[bel[u]].push_back({bel[v],id});
        }
    }
    for(int i=1;i<=n;++i){
        a[bel[i]].push_back(col[i]);
    }
    int ori=0;
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            A.add(i,0);
            init(i,0);
            MX=A.MX;
            ori+=A.MX;
            DFS(i,0);
            clear();
            A.del(i,0);
        }
    }
    for(int i=1;i<=m;++i){
        cout<<ans[i]+ori<<"  \n"[i==m];
    }
    for(int i=1;i<=n;++i){
        a[i].clear();
        E[i].clear();
        e[i].clear();
        sk[i]=0;
        ip=0;
        top=0;
        tot=0;
        vis[i]=0;
        siz[i]=0;
        now.clear();
        MX=0;
        ans[i]=bel[i]=col[i]=dfn[i]=low[i]=0;
    }
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
}