#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k, a, b;
ll dp[300005][1<<5];
vector<int> adj[300005];
int col[300005];
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m >> k;
for(int i=1;i<=n;i++) {
cin >> col[i];
col[i]--;
dp[i][1<<col[i]] = 1;
}
while(m--) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
ll sum = 0;
for(int cst = 0; cst < (1 << k); cst++) {
for(int i=1;i<=n;i++) {
for(auto &e:adj[i]) {
if((cst >> col[e]) & 1) continue;
dp[e][cst | (1 << col[e])] += dp[i][cst];
}
sum += dp[i][cst];
//cout << dp[i][cst] << ' ';
}
//cout << '\n';
}
cout << sum-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... |