#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 300005
#define LOG 17
using namespace std;
const ll inf = 1e9;
ll getbit(ll mask, ll i) {
return (mask >> i) & 1;
}
ll onbit(ll mask, ll i) {
return mask | (1 << i);
}
bool ghuy4g;
ll n, m, k;
vector<ll> adj[N];
pii canh[N];
ll d[N][(1 << 5)], c[N], d1[N][(1 << 5)];
void bfs() {
for (int i = 1; i <= n; i ++) {
d[i][onbit(0, c[i])] = 1;
}
ll ans = 0;
for (int turn = 2; turn <= k; turn ++) {
for (int i = 1; i <= n; i ++) {
for (int mask = 0; mask < (1 << k); mask ++) {
d1[i][mask] = d[i][mask];
d[i][mask] = 0;
}
}
for (int i = 1; i <= m; i ++) {
ll u, v;
u = canh[i].fi, v = canh[i].se;
for (int mask = 0; mask < (1 << k); mask ++) {
// d[v][onbit(mask, c[v])] += d[u][mask];
if (getbit(mask, c[v]) == 0) {
/*if (v == 2 && onbit(mask, c[v]) == 3) {
cout << "here i " << turn << " " << u << " " << d1[u][mask] << " " << d[v][onbit(mask, c[v])] << endl;
}*/
d[v][onbit(mask, c[v])] += d1[u][mask];
}
if (getbit(mask, c[u]) == 0) {
/*if (u == 2 && onbit(mask, c[u]) == 3) {
cout << "here i " << turn << " " << v << " " << d1[v][mask] << " " << d[u][onbit(mask, c[u])] << endl;
}*/
d[u][onbit(mask, c[u])] += d1[v][mask];
}
}
}
for (int i = 1; i <= n; i ++) {
for (int mask = 0; mask < (1 << k); mask ++) {
ans += d[i][mask];
/*if (d[i][mask]) {
cout << i << " " << bitset<3>(mask) << " " << d[i][mask] << endl;
}*/
}
}
}
/*for (int i = 1; i <= n; i ++) {
for (int mask = 0; mask < (1 << k); mask ++) {
ans += d[i][mask];
if (d[i][mask]) {
cout << i << " " << bitset<3>(mask) << " " << d[i][mask] << endl;
}
}
}*/
cout << ans << endl;
}
bool klinh;
signed main() {
// freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
//srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++) {
cin >> c[i];
c[i] -- ;
}
for (int i = 1; i <= m; i ++) {
ll u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
canh[i] = {u, v};
}
bfs();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}
