看到此题，我的评价是我国 OI 遥遥领先。

注意到颜色个数只有 5，考虑状压。

$dp$ 数组第一维为当前枚举到第二个点，第二维则是当前该路径中的所有点中的颜色状态，其中的值即为当前状态的路径总数。

当该状态中的颜色个数超过 2 时，发现由于我们保证了颜色互不相同，所以此时的点的个数也超过了 2 将当前状态的 $dp$ 值累加答案即可。

状态转移极为简单，留给读者自行思考。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,a[300005],dp[300005][100],ans; 
vector<int>vec[300005];
int lowbit(int x)
{
    return x&-x;
}
int solve(int x)
{
	int cnt=0;
	while(x>0) x-=lowbit(x),cnt++;
	return cnt;
}
signed main() 
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i],dp[i][1<<(a[i]-1)]=1;
    for(int i=1;i<=m;i++)
    {
    	int a,b;
    	cin>>a>>b;
    	vec[a].push_back(b);
    	vec[b].push_back(a); 
	}
	for(int i=0;i<(1<<k);i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(solve(i)>1) ans+=dp[j][i];
			for(auto it:vec[j])
			{
				if(i&(1<<(a[it]-1))) continue;
				dp[it][i+(1<<(a[it]-1))]+=dp[j][i];
			}
		}
	}
	cout<<ans;
    return 0;
}