#include<iostream> #include<vector> #define int long long const int maxn = 3e5 + 5; using namespace std; vector<int> g[maxn]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vector<int> a(n); for (auto& x : a) { cin >> x; --x; } for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<vector<int>> dp(n + 1, vector<int>(1ll << k, 0)); for (int i = 1; i <= n; ++i) dp[i][((1 << k) - 1) ^ (1 << a[i - 1])] = 1; for (int mask = (1 << k) - 1; mask >= 0; --mask) for (int i = 1; i <= n; ++i) if (!(mask & (1ll << a[i - 1]))) { dp[i][mask] = 1; for (auto x : g[i]) dp[i][mask] += dp[x][mask | (1ll << a[i - 1])]; } int ans = 0; for (int i = 1; i <= n; ++i) ans += dp[i][0]; cout << ans - n; }