RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int long long
const ll MAXN=2e6+5,MAXM=2e6+5;
ll n,m,k,x,y;
int col[MAXN];
struct edge{
	int u,v,w,nxt;
	int 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;
int head[MAXN],edge_num;
int head_new[MAXN],edge_num_new;
void add_edge(int From,int 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(int From,int To,int 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<int> vec_col[MAXN];
vector<edge> vec_edge[MAXN];
bool check[MAXN];
int fa[MAXN];
int Find(int num){
	return num==fa[num]?num:fa[num]=Find(fa[num]);
}
ll ans;
ll sum,cnt;
int p_col[MAXN],tot;
int rt[MAXN];
int rev[MAXN];
void paint(int now,bool now_c,int 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<int,bool> mp_rt;
int p_rev[MAXN];
struct node{
	int id,now_c;
};
bool vvv[MAXN];
queue<node> q;
bool bfs(int st){
	for(auto x:mp_rt)p_rev[x.first]=-1,vvv[x.first]=0;
	p_rev[n+1]=-1,vvv[n+1]=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=now.now_c^new_e[i].w;
				if(p_rev[new_e[i].v]!=reg_rev)return 0;
				continue;
			}
			p_rev[new_e[i].v]=p_rev[now.id]^new_e[i].w;
			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+1;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+2;i++)head[i]=0,head_new[i]=0;
	edge_num=edge_num_new=0;
	for(int i=1;i<=ttt_cnt;i++)add_edge(ttt[i].u,ttt[i].v);
	sort(e+1,e+1+edge_num);
	ll qaq=0;
	for(int i=1,j;i<=edge_num;i=j+1){
		if(mp_rt.size())for(auto x:mp_rt)head_new[x.first]=0,p_rev[x.first]=0;
		head_new[n+1]=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++;
		qaq=1;
		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,n+1,1),add_edge_new(rt_v,n+1,1),add_edge_new(n+1,rt_u,1),add_edge_new(n+1,rt_v,1),p_rev[n+1]=-2;//nrev
		}
		bool fl=1;
		for(auto x:mp_rt){
			if(p_rev[x.first]!=-2)continue;
			fl&=bfs(x.first);
		}
		ans+=fl;
	}
	ans=ans-cnt+(1ll*sum*(sum-1))/2ll;
//	if(ans==494372)ans=494070;//here 
	cout<<ans;
	return 0;
} 

给个hack，或者指出错误都可以/dk