#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int mod=1e9+7, maxn=3e5+5;
int n, m, k, c[maxn], u, v, tmp, order[125][10], p[10], NEXT[10], now;
vector<int> adj[maxn];
bool vis[10];
ll byk[maxn], tot[10], ans;
queue<int> q;
string s;
map<string, bool> pernah;
void perm(int idx) {
if(idx>k) {
tmp++;
for(int i=1; i<=k; i++) order[tmp][i]=p[i];
return;
}
for(int i=1; i<=k; i++) {
if(!vis[i]) {
vis[i]=true;
p[idx]=i;
perm(idx+1);
vis[i]=false;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m >> k;
for(int i=1; i<=n; i++) cin >> c[i];
while(m--) {
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
perm(1);
for(int i=1; i<=tmp; i++) {
for(int j=1; j<=k; j++) NEXT[order[i][j]]=order[i][j+1], tot[j]=0;
for(int j=1; j<=n; j++) {
if(c[j]==order[i][1]) {
q.push(j);
byk[j]=1;
} else byk[j]=-1;
}
while(!q.empty()) {
now=q.front();
tot[c[now]]+=byk[now];
q.pop();
for(auto nxt:adj[now]) {
if(c[nxt]==NEXT[c[now]]) {
if(byk[nxt]==-1) {
byk[nxt]=byk[now];
q.push(nxt);
} else byk[nxt]+=byk[now];
}
}
}
s=order[i][1]-'0';
for(int j=2; j<=k; j++) {
s+=order[i][j]-'0';
if(!pernah[s]) {
ans+=tot[order[i][j]];
pernah[s]=true;
}
}
}
cout << ans << '\n';
}
