#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
vector<int> a(2 * m), b(2 * m), c(n + 1);
for (int i = 1; i <= n; i++)
cin >> c[i], c[i]--;
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i];
b[i + m] = a[i];
a[i + m] = b[i];
}
vector<vector<ll>> dp(n + 1, vector<ll>(1 << k));
ll ans = 0;
for (int i = 1; i < 1 << k; i++) {
if (__builtin_popcount(i) == 1) {
for (int v = 1; v <= n; v++)
if (i == 1 << c[v])
dp[v][i] = 1;
}
else {
for (int j = 0; j < 2 * m; j++) {
if (i >> c[a[j]] & 1)
dp[a[j]][i] += dp[b[j]][i ^ 1 << c[a[j]]];
}
for (int v = 1; v <= n; v++)
ans += dp[v][i];
}
}
cout << ans;
}
