题意简述
有 \(n\) 道题，每道题有 \(10^5\) 个选项，其中选项 \(a_i\) 是正确的。
再给定 \(m\) 条限制 \(u_i,v_i\)，表示题目 \(u_i,v_i\) 必须要选择相同的选项。
对于 \(m\) 条限制，求出若去掉这条限制，最多能回答多少问题。
多组数据。
\(n,m,a_i\le 10^5,\sum n,\sum m\le 10^6\)。
分析
将限制建边，则一个连通块之内的点只能选一个共同的选项，那么我们肯定要选连通块内出现次数（有多少个题是以它为正确选项）最多的。
考虑删边会发生什么。
如果它是割边，那么会分出两个新的连通块。如果不是，什么都不会发生。
考虑如何求两个新连通块内的出现次数最多选项的出现次数。如果我们有整个连通块的答案和子树内的答案，我们就可以推出子树外的答案。
求子树内的答案，可以用 dsu on tree。
我们将原图边双缩点，那么原图会形成一个森林。对森林做 dsu on tree，割边就用分出的新的连通块的答案加上其他连通块的答案，非割边就是原来的连通块的答案。
多测清空要彻底！上限是 n 是 m 要分清！注意细节！有一个坚强的肝！
点击查看代码
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define FlushIn fread(Fread::ibuf,1,1<<21,stdin)
#define FlushOut fwrite(Fwrite::obuf,1,Fwrite::S-Fwrite::obuf,stdout)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=d)
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
bool smallingll(long long x,long long y){return x<y;}
namespace Fread {
const int SIZE=1<<21;
char ibuf[SIZE],*S,*T;
inline char getc(){if(S==T){T=(S=ibuf)+fread(ibuf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite{
const int SIZE=1<<21;
char obuf[SIZE],*S=obuf,*T=obuf+SIZE;
inline void flush(){fwrite(obuf,1,S-obuf,stdout);S=obuf;}
inline void putc(char c){*S++=c;if(S==T)flush();}
struct NTR{~NTR(){flush();}}ztr;
}
/*#ifdef ONLINE_JUDGE
#define getchar Fread::getc
#define putchar Fwrite::putc
#endif*/
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=1e5+5,maxm=4e5+5,inf=0x3f3f3f3f,lim=1e5;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m,c[maxn];
int ans[maxn],bns[maxn];
struct edge{
int to,nxt,id;
bool bri;
}a[maxn<<1];
int head[maxn],edges;
void add_edge(int x,int y,int z){
a[++edges]=(edge){y,head[x],z};
head[x]=edges;
}
namespace Tarjan{
int dfn[maxn],low[maxn],dfncnt;
int sc,scc[maxn];
vector<int>bcc[maxn];
vector<pii>G[maxn];
void tarjan(int x,int y){
dfn[x]=low[x]=++dfncnt;
graph(i,x,head,a){
int u=a[i].to;
if(!dfn[u]){
tarjan(u,x),low[x]=min(low[x],low[u]);
if(dfn[x]<low[u])a[i].bri=a[i^1].bri=1;
}else if(u^y)low[x]=min(low[x],dfn[u]);
}
}
bool vis[maxn];
void _dfs_(int x){
vis[x]=1,scc[x]=sc,bcc[sc].pb(x);
graph(i,x,head,a){
int u=a[i].to;
if(!a[i].bri&&!vis[u])_dfs_(u);
}
}
}using namespace Tarjan;
namespace DSU{
int d[maxn];//总
int b[maxn];//子树
int cntb[maxn],cntd[maxn];//出现次数
int mx,mn;//mx子树外，mn子树内
int bel[maxn],bv;
void add_d(int x){d[cntd[x]]--,cntd[x]++,d[cntd[x]]++;if(d[mx+1])mx++;}
void del_d(int x){d[cntd[x]]--,cntd[x]--,d[cntd[x]]++;if(!d[mx])mx--;}
void add_b(int x){b[cntb[x]]--,cntb[x]++,b[cntb[x]]++;if(b[mn+1])mn++;}
void del_b(int x){b[cntb[x]]--,cntb[x]--,b[cntb[x]]++;if(!b[mn])mn--;}
void add(int x){add_b(x),del_d(x);}
void del(int x){del_b(x),add_d(x);}
void stdfs(int x,int y){
vis[x]=1;
for(int u:bcc[x])add_d(c[u]);
for(pii i:G[x])if(i.fi^y)stdfs(i.fi,x),bel[i.se]=bv;
}
void eddfs(int x,int y){
for(int u:bcc[x])del_d(c[u]);
for(auto i:G[x])if(i.fi^y)eddfs(i.fi,x);
}
int siz[maxn],son[maxn],E[maxn];
void __dfs(int x,int y){
siz[x]=bcc[x].size();
for(auto i:G[x])if(i.fi^y){
int u=i.fi;__dfs(u,x);
siz[x]+=siz[u];
if(siz[u]>siz[son[x]])son[x]=u,E[x]=i.se;
}
}
void adfs(int x,int y){
for(int u:bcc[x])add(c[u]);
for(pii i:G[x])if(i.fi^y)adfs(i.fi,x);
}
void cdfs(int x,int y){
for(int u:bcc[x])del(c[u]);
for(pii i:G[x])if(i.fi^y)cdfs(i.fi,x);
}
void dfs(int x,int y,bool ok=0){
for(pii i:G[x])if(i.fi!=y&&i.fi!=son[x])dfs(i.fi,x,0);
for(pii i:G[x])if(i.fi!=y&&i.fi!=son[x])adfs(i.fi,x),ans[i.se]=mx+mn,cdfs(i.fi,x);
if(son[x])dfs(son[x],x,1);
ans[E[x]]=mx+mn;
for(pii i:G[x])if(i.fi!=y&&i.fi!=son[x])adfs(i.fi,x);
for(int u:bcc[x])add(c[u]);
if(!ok)cdfs(x,y);
}
}using namespace DSU;
bool nsbsa[maxn];
map<int,int>re[maxn];
void init(){
edges=1,dfncnt=sc=bv=0;
rep(i,1,n)G[i].clear(),bcc[i].clear(),re[i].clear();
rep(i,1,n)dfn[i]=low[i]=head[i]=vis[i]=scc[i]=siz[i]=son[i]=E[i]=0;
rep(i,1,m)ans[i]=bel[i]=nsbsa[i]=0;
}
void solve_the_problem(){
n=rd(),m=rd();rep(i,1,n)c[i]=rd();
init();
rep(i,1,m){
int x=rd(),y=rd();if(re[x][y]){nsbsa[re[x][y]]=1,nsbsa[i]=1;continue;}
re[x][y]=re[y][x]=i;
add_edge(x,y,i),add_edge(y,x,i);
}
rep(i,1,n)if(!dfn[i])tarjan(i,0);
rep(i,1,n)if(!vis[i])++sc,_dfs_(i);
rep(i,1,n){
graph(j,i,head,a){
int u=a[j].to;
if(a[j].bri)G[scc[i]].pb(mp(scc[u],a[j].id));
}
}
rep(i,1,n)vis[i]=0;
int sum=0;
rep(i,1,sc)if(!vis[i]){
mx=mn=0,++bv;
stdfs(i,0),__dfs(i,0);
sum+=mx,bns[bv]=mx;
dfs(i,0);
eddfs(i,0);
}
// rep(i,1,bv)write(bns[i],32);P__;
// rep(i,1,m)write(ans[i],32);P__;
rep(i,1,m){
if(!nsbsa[i]){
if(!ans[i])ans[i]+=sum;
else ans[i]+=sum-bns[bel[i]];
}else{
ans[i]=sum;
}
}
rep(i,1,m)write(ans[i],i==m?0:32);P__;
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
// fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=rd();while(_--)solve_the_problem();
}
/*
1
8 6
1 1 4 5 1 4 1 9
1 2
1 3
2 3
2 5
3 4
6 7
*/