可撤销并查集好题。
首先考虑如果已经确定选哪两组，该怎么判断。发现是一个二分图判定的问题，拓展域并查集即可。
那如果要求出所有可能的两组的答案怎么办。首先，如果两组中至少有一组，在只加入组内边时就已经不可能是二分图了，这种情况就显然是不行的。
否则，可以考虑预先加入所有组内的连边，枚举每一种出现过的组之间的边，并加入所有同种的边，再判定是否是二分图。
但是这样有个问题：判定每一对组时，都要将并查集数组初始化，时间会爆炸。于是考虑使用可撤销并查集撤销加边操作，就可以解决了。
注意还要判断之间没有连边的组，这种就直接判断各自是否是二分图即可。
总时间复杂度 \(O(m\log(n+m))\)。
code：
点击查看代码
int n,m,k,s,top,fa[N],st[N],vl[N],c[N];
bool vis[N];
mt19937 rnd(time(0));
struct node{int u,v;}e[N];
int find(int x){return fa[x]==x?x:find(fa[x]);}
il void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(vl[x]>vl[y])swap(x,y);
fa[x]=y,st[++top]=x;
}
il bool cmp(node x,node y){return c[x.u]!=c[y.u]?c[x.u]<c[y.u]:c[x.v]<c[y.v];}
void Yorushika(){
scanf("%d%d%d",&n,&m,&k);
rep(i,1,n)scanf("%d",&c[i]);
rep(i,1,n*2)fa[i]=i,vl[i]=rnd();
mems(vis,1);
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
if(c[u]==c[v]){
if(find(u)==find(v))vis[c[u]]=0;
merge(u,v+n),merge(u+n,v);
}else{
if(c[u]>c[v])swap(u,v);
e[++s]=(node){u,v};
}
}
sort(e+1,e+s+1,cmp);
ll ans=0;
rep(i,1,k)ans+=vis[i];
ans=ans*(ans-1)/2;
bool fl=1;
top=0;
rep(i,1,s){
int u=e[i].u,v=e[i].v;
if(find(u)==find(v))fl=0;
merge(u,v+n),merge(u+n,v);
if(c[u]==c[e[i+1].u]&&c[v]==c[e[i+1].v])continue;
if(!vis[c[u]]||!vis[c[v]]){
while(top)fa[st[top]]=st[top],top--;
fl=1;continue;
}
ans-=!fl,fl=1;
while(top)fa[st[top]]=st[top],top--;
}
printf("%lld\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}