RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const ll MAXN=5e5+5,MAXM=2e6+5;
ll n,m,k,x,y;
ll col[MAXN];
struct edge{
	ll u,v,w,nxt;
	ll col_u,col_v;
	bool operator < (const edge &oth)const{
		return col_u==oth.col_u?col_v<oth.col_v:col_u<oth.col_u;
	}
}e[MAXM],new_e[MAXM],ttt[MAXM];
ll ttt_cnt;
ll head[MAXN],edge_num;
ll head_new[MAXN],edge_num_new;
void add_edge(ll From,ll To){
	edge_num++;
	e[edge_num].u=From;
	e[edge_num].col_u=col[From];
	e[edge_num].v=To;
	e[edge_num].col_v=col[To];
	e[edge_num].nxt=head[From];
	head[From]=edge_num;
	return;
}
void add_edge_new(ll From,ll To,ll Len){
	edge_num_new++;
	new_e[edge_num_new].u=From;
	new_e[edge_num_new].col_u=col[From];
	new_e[edge_num_new].v=To;
	new_e[edge_num_new].col_v=col[To];
	new_e[edge_num_new].w=Len;
	new_e[edge_num_new].nxt=head_new[From];
	head_new[From]=edge_num_new;
	return;
} 
vector<ll> vec_col[MAXN];
vector<edge> vec_edge[MAXM];
bool check[MAXN];
ll fa[MAXN];
ll Find(ll num){
	return num==fa[num]?num:fa[num]=Find(fa[num]);
}
ll ans;
ll sum,cnt;
ll p_col[MAXN],tot;
ll rt[MAXN];
ll rev[MAXN];
void paint(ll now,bool now_c,ll color){
	if(p_col[now]!=-1||col[now]!=color)return;
	p_col[now]=now_c;
	rt[now]=tot;
	for(int i=head[now];i;i=e[i].nxt){
		if(p_col[e[i].v]!=-1||col[e[i].v]!=color)continue;
		paint(e[i].v,now_c^1,color);
	}
	return;
}
map<ll,bool> mp_rt;
ll p_rev[MAXN];
struct node{
	ll id,now_c;
};
bool vvv[MAXN];
queue<node> q;
bool bfs(ll st){
	for(auto x:mp_rt)p_rev[x.first]=-1,vvv[x.first]=0;
	p_rev[st]=0;
	while(q.size())q.pop();
	q.push((node){st,0});
	while(q.size()){
		node now=q.front();
		q.pop();
		vvv[now.id]=1;
		for(int i=head_new[now.id];i;i=new_e[i].nxt){
			if(vvv[new_e[i].v]){
				bool reg_rev=p_rev[now.id]^new_e[i].w;
				if(p_rev[new_e[i].v]!=reg_rev)return 0;
			}
			p_rev[new_e[i].v]=p_rev[now.id]^new_e[i].w;
			if(!vvv[new_e[i].v])q.push((node){new_e[i].v,p_rev[new_e[i].v]});
		}
	}
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>col[i];
		vec_col[col[i]].push_back(i);
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		add_edge(x,y);
		add_edge(y,x);
		if(col[x]==col[y]){
			vec_edge[col[x]].push_back(e[edge_num-1]); 
			vec_edge[col[x]].push_back(e[edge_num]); 
		}
	}
	for(int i=1;i<=k;i++){
		for(ll x:vec_col[i-1])head_new[x]=0;
		for(ll x:vec_col[i])fa[x]=x;
		edge_num_new=0;
		for(edge x:vec_edge[i])add_edge_new(x.u,x.v,0);
		for(ll x:vec_col[i]){
			ll res=new_e[head_new[x]].v;
			if(check[i])break;
			for(int j=head_new[x];j;j=new_e[j].nxt){
				if(Find(new_e[j].v)==Find(x)){
					check[i]=1;
					break;
				}
				fa[Find(res)]=Find(new_e[j].v);
				res=new_e[j].v;
			}
		}
		sum+=check[i];
	}
	for(int i=1;i<=n;i++)p_col[i]=-1;
	for(int i=1;i<=k;i++){
		if(!check[i]){
			for(auto x:vec_col[i]){
				if(p_col[x]==-1){
					tot++;
					paint(x,0,i);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)rev[i]=-1;
//	cout<<"tot "<<tot<<endl;
//	cout<<"rt\n";
//	for(int i=1;i<=n;i++)cout<<rt[i]<<" ";
//	cout<<endl<<"col\n";
//	for(int i=1;i<=n;i++)cout<<p_col[i]<<" ";
//	cout<<endl;
	sum=k-sum;
	for(int i=1;i<=edge_num;i++)if(e[i].col_u!=e[i].col_v)ttt[++ttt_cnt]=e[i];
	for(int i=1;i<=n;i++)head[i]=0;
	edge_num=0;
	for(int i=1;i<=ttt_cnt;i++)add_edge(ttt[i].u,ttt[i].v);
	stable_sort(e+1,e+1+edge_num);
	for(int i=1,j;i<=edge_num;i=j+1){
		for(auto x:mp_rt)head_new[x.first]=0;
		edge_num_new=0;
		mp_rt.clear(); 
		for(j=i;e[j].col_u==e[i].col_u&&e[j].col_v==e[i].col_v&&j<=edge_num;j++);
		j--;
		if(e[i].col_u>e[i].col_v||check[e[i].col_u]||check[e[i].col_v])continue;
		cnt++;
		for(int k=i;k<=j;k++){
			ll rt_u=rt[e[k].u],rt_v=rt[e[k].v];
			mp_rt[rt_u]=mp_rt[rt_v]=1;
			p_rev[rt_u]=p_rev[rt_v]=-2;
			if(p_col[e[k].u]==p_col[e[k].v])add_edge_new(rt_u,rt_v,1),add_edge_new(rt_v,rt_u,1);//rev
			else add_edge_new(rt_u,rt_v,0),add_edge_new(rt_v,rt_u,0);//nrev
		}
		bool fl=1;
		for(auto x:mp_rt){
			if(p_rev[x.first]!=-2)continue;
			fl&=bfs(x.first);
		}
		ans+=fl;
	}
	cout<<ans+(sum*(sum-1))/2-cnt;
	return 0;
} 

不知道哪个细节出问题了/ll