#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define mod 998244353
#define MAX 2000
int main(){
ll n, m, k, a, b;
cin>>n>>m>>k;
vector<vector<int>> v(n + 1);
vector<int> col(n + 1, 0);
for (int i = 1; i <= n; i++){
cin>>col[i];
col[i]--;
}
for (int i = 0; i < m; i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
int ti = (1<<k);
vector<vector<ll>> dp(n + 1, vector<ll>(ti, 0));
for (int i = 1; i <= n; i++){
dp[i][(1<<col[i])]++;
}
for (int i = 0; i < ti; i++){
for (int j = 1; j <= n; j++){
for (auto el : v[j]){
int val = i & (1<<col[el]);
if (val != 0) continue;
int to = i | (1<<col[el]);
dp[el][to] += dp[j][i];
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 0; j < ti; j++) ans += dp[i][j];
}
cout<<ans - n<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |