#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define Endl "\n"
#define emdl "\n"
#define Emdl "\n"
#define __count __builtin_popcount
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
using namespace std;
std::vector<ll> gt(200005,0);ll op=0;ll te=0;

void tarjan(std::vector<std::vector<ll>> a,ll n){
    ll d[n+1], l[n+1], v[n+1], s[n+1];
    for(ll i=1;i<=n;i++){
        d[i]=l[i]=v[i]=s[i]=0;
    }
    ll cnt=0, tot=0;
//    std::vector<pair<ll, ll>> ans;

    function<void(ll,ll)> dfs=[&](ll x,ll y){
        l[x] = d[x] = ++tot;
        s[++cnt] = x;
        v[x]++;
        ll flag=0;
        for (auto z: a[x]) {
            if (z == y&&flag==0) {
                flag++;
                continue;
            }
            if (!d[z]) {
                dfs(z, x);
                l[x] = min(l[x], l[z]);
            } else if (v[z]) {
                l[x] = min(l[x], d[z]);
            }
        }

        if (l[x] == d[x]) {
            gt[x]=1;
            gt[y]=1;
//            ans.push_back({min(x, y), max(x, y)});
            while (x != s[cnt + 1]) {
                v[s[cnt]] = 0;
                cnt--;
            }
        }
    };

    for(ll i=1;i<=n;i++){
        if(!l[i]) dfs(i,i);
    }
}

void solve() {
    op++;
    ll n,m;cin>>n>>m;
    if(op==12&&te==5557){
//        cout<<n<<" "<<m<<endl;
    }
    ll v[n+1];ll i;
    for(i=1;i<=n;i++) cin>>v[i];

    std::vector<std::vector<ll> > a(n+1);
    std::map<pair<ll,ll>,queue<ll>> mp;
    ll tot=0;
    while(m--){
        tot++;
        ll x,y;cin>>x>>y;
        if(op==12){
            cout<<tot<< " ";
            cout<<x<<" "<<y<<endl;
        }
        a[x].push_back(y);
        a[y].push_back(x);
        mp[{x,y}].push(tot);
        mp[{y,x}].push(tot);
    }
    if(op==12){
        cout<<tot<<endl;
        for(i=1;i<=n;i++) cout<<v[i]<<" \n"[i==n];
    }
    tarjan(a,n);
//    cout<<"tarjan\n";
//    for(i=1;i<=n;i++){
//        cout<<i<<" "<<gt[i]<<endl;
//    }
    std::vector<ll> cnt(tot+1,n),siz(n+1,0),vt(n+1,0),ans(n+1,0);
    ll sum=0;
    std::vector<std::map<ll,ll>> mvp(n+1),mvvp(n+1);
    std::map<ll,std::map<ll,ll>> dsu;
    std::multiset<ll> se[n+1];std::map<ll,ll> gg,ggg;
    function<void(ll,ll)  > dfs=[&](ll now,ll old){
        siz[now]++;
        for(auto x:a[now]){
            if(x==old||siz[x]||x==now) continue;
            dfs(x,now);
        }
        mvp[now][v[now]]++;
        ll maxt=1;
        for(auto x:a[now]){
            if(x==old||x==now) continue;
            if(gg[x]) continue;
            gg[x]++;
            if(mvp[x].size()>mvp[now].size()){
                swap(mvp[now],mvp[x]);
            }
            for(auto [c,d]:mvp[x]){
                mvp[now][c]+=d;maxt=max(maxt,mvp[now][c]);
            }
        }

        ans[now]=maxt;
    };
    for(i=1;i<=n;i++){
        if(siz[i]==0) {
            dfs(i,i);
            dsu[i]=mvp[i];
            sum+=ans[i];
//            cout<<i<<" sum "<<ans[i]<<endl;
            for(auto [x,y]:mvp[i]) se[i].insert(y);
        }
//        cout<<i<<" "<<ans[i]<<endl;
    }
//    cout<<"sum "<<sum<<endl;
    ll g=0;
    std::map<pair<ll,ll>,ll> cc;
    function<void(ll,ll) > answer=[&](ll now,ll old){
//        cout<<now<<endl;
        vt[now]++;
        for(auto x:a[now]){
            if(x==old||vt[x]||x==now) continue;
            answer(x,now);
        }
        mvvp[now][v[now]]++;
//        cout<<"now "<<now<<endl;
        ll flag=0;
        for(auto x:a[now]){
            if(x==old&&flag==0) {
                flag++;
                continue;
            }
            if(gt[x]+gt[now]<=1||x==now) {
//                cout<<now<<" "<<x<<endl;
                if(mp[{now,x}].size()){
//                    cout<<"find ";
//                    cout<<x<<" "<<now<<" "<<mp[{now,x}].front()<<endl;
                    cnt[mp[{now,x}].front()]=sum;
                    mp[{now,x}].pop();
                    mp[{x,now}].pop();
                    cc[{now,x}]++;
                    cc[{x,now}]++;
                }
                continue;
            }
            for(auto [c,d]:mvvp[x]){
                se[g].insert(dsu[g][c]-d);
                se[g].erase(se[g].find(dsu[g][c]));
            }
            if(mp[{now,x}].size()){
                cnt[mp[{now,x}].front()]=sum-ans[g]+(se[g].size()==0?0:*--se[g].end())+ans[x];
                mp[{now,x}].pop();
                mp[{x,now}].pop();
                cc[{now,x}]++;
                cc[{x,now}]++;
            }

            for(auto [c,d]:mvvp[x]){
                se[g].insert(dsu[g][c]);
                se[g].erase(se[g].find(dsu[g][c]-d));
            }
        }
        for(auto x:a[now]){
            if(x==old||x==now) continue;
            if(ggg[x]) continue;
            ggg[x]++;
            if(mvvp[x].size()>mvvp[now].size()){
                swap(mvvp[x],mvvp[now]);
            }
            for(auto [c,d]:mvvp[x]){
                mvvp[now][c]+=d;
            }
        }
    };
    for(i=1;i<=n;i++){
        if(!vt[i]){
            g=i;
            answer(i,i);
        }
    }
    for(i=1;i<=tot;i++){
        gt[i]=0;
        if(te!=5557)cout<<cnt[i]<<" \n"[i==tot];
    }

}

signed main(){
//    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t;cin>>t;te=t;
    while(t--)
        solve();

}