RT

#include<bits/stdc++.h>
#include<queue>
#include<list>
using namespace std;
typedef long long ll;
const int MAXN=1e6+5,MAXM=4e6+5;
int n,m,k,x,y;
int col[MAXN];
struct edge{
	int u,v,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[MAXN];
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){
	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].nxt=head_new[From];
	head_new[From]=edge_num_new;
	return;
} 
list<int> vec_col[MAXN];
list<edge> vec_edge[MAXN];
bool check[MAXN];
int fa[MAXN];
int Find(ll num){
	return num==fa[num]?num:fa[num]=Find(fa[num]);
}
ll ans;
unordered_map<int,bool> reg_point;
ll not_null,is_null;
bool vis_col[MAXN];
ll sum,cnt;
int res;
int 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;
		vis_col[col[x]]=vis_col[col[y]]=1;
		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(int x:vec_col[i-1])head_new[x]=0,fa[x]=0;
		for(int x:vec_col[i])fa[x]=x;
		edge_num_new=0;
		for(edge x:vec_edge[i])add_edge_new(x.u,x.v);
		for(int x:vec_col[i]){
			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];
	}
	sum=k-sum;
	sort(e+1,e+1+edge_num);
	for(int i=1,j;i<=edge_num;i=j+1){
		for(auto x:reg_point)head_new[x.first]=0,fa[x.first]=0;
		reg_point.clear();
		edge_num_new=0;
		for(j=i;e[j].col_u==e[i].col_u&&e[j].col_v==e[i].col_v;j++){
			reg_point[e[j].u]=1;reg_point[e[j].v]=1;
			add_edge_new(e[j].u,e[j].v); 
			add_edge_new(e[j].v,e[j].u); 
		}
		j--;
		if(e[i].col_u>=e[i].col_v||check[e[i].col_u]||check[e[i].col_v])continue;
		cnt++;
		bool fl=0;
		for(auto x:vec_edge[e[i].col_u]){
			add_edge_new(x.u,x.v);
			reg_point[x.u]=reg_point[x.v]=1;
		}
		for(auto x:vec_edge[e[i].col_v]){
			add_edge_new(x.u,x.v);
			reg_point[x.u]=reg_point[x.v]=1;
		}
		for(auto x:reg_point)fa[x.first]=x.first;
		for(auto x:reg_point){
			int now=x.first;
			res=new_e[head_new[now]].v;
			if(fl)break;
			for(int k=head_new[now];k;k=new_e[k].nxt){
				if(Find(new_e[k].v)==Find(now)){
					fl=1;
					break;
				}
				fa[Find(res)]=Find(new_e[k].v);
				res=new_e[k].v;
			}
		}
		ans+=(!fl);
	}
	cout<<ans+(sum*(sum-1))/2-cnt;
	return 0;
} 

感觉写法很迷，是不是复杂度错了（