#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int NMAX = 3e5;
const int MSK = (1LL << 5);
const int BITS = 5;
using namespace std;
vector<int> G[NMAX + 5];
vector<int> M[BITS + 5];
int dp[NMAX + 5][MSK + 5], c[NMAX + 5], n, m, k;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
--c[i];
dp[i][(1LL << c[i])] = 1;
}
for (int i = 0, u, v; i < m; ++i) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int msk = 0; msk < (1LL << k); ++msk)
M[__builtin_popcountll(msk)].push_back(msk);
for (int popcnt = 0; popcnt < k; ++popcnt){
for (auto &msk : M[popcnt]) {
for (int u = 1; u <= n; ++u) {
if (dp[u][msk] == 0) continue;
for (auto &nxt : G[u]) {
if (!(msk & (1LL << c[nxt]))) {
int new_msk = (msk ^ (1LL << c[nxt]));
dp[nxt][new_msk] += dp[u][msk];
}
}
}
}
}
int total_ways = 0;
for (int u = 1; u <= n; ++u) {
for (int msk = 0; msk < (1LL << k); ++msk) {
if (__builtin_popcountll(msk) >= 2)
total_ways += dp[u][msk];
}
}
cout << total_ways << '\n';
return 0;
}
