#include <iostream>
#include <vector>
#include <vector>
using namespace std;
// Masala chegaralari: N va M 300,000 gacha, K esa 5 gacha.
// DP jadvali: dp[mask][u] -> mask to'plamidagi ranglar ishlatilgan va u uchida tugaydigan yo'llar soni.
long long dp[32][300005];
int color[300005];
vector<int> adj[300005];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
// Har bir uchning rangini o'qiymiz (0 dan k-1 gacha o'tkazamiz)
for (int i = 1; i <= n; i++) {
cin >> color[i];
color[i]--; // Bit siljitish oson bo'lishi uchun 0-indeksga o'tkazamiz
dp[1 << color[i]][i] = 1; // Boshlang'ich holat: har bir uch o'zi bitta yo'l (uzunligi 1)
}
// Qirralarni o'qiymiz
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// DP: Maskalar bo'yicha sikl (1 dan 2^k - 1 gacha)
// Avval kichik maskalarni hisoblasak, keyin kattaroqlarini hisoblashda tayyor ma'lumot bo'ladi.
for (int mask = 1; mask < (1 << k); mask++) {
for (int u = 1; u <= n; u++) {
if (dp[mask][u] == 0) continue;
// u uchidan qo'shni v uchiga o'tishga harakat qilamiz
for (int v : adj[u]) {
int c_v = color[v];
// Agar v ning rangi hali mask ichida bo'lmasa, yangi yo'l hosil qilamiz
if (!(mask & (1 << c_v))) {
dp[mask | (1 << c_v)][v] += dp[mask][u];
}
}
}
}
long long total_paths = 0;
// Natijani hisoblash: maskada kamida 2 ta bit (rang) bo'lgan barcha holatlarni qo'shamiz
for (int mask = 1; mask < (1 << k); mask++) {
// __builtin_popcount - bu bitlar sonini sanaydigan funksiya
if (__builtin_popcount(mask) >= 2) {
for (int i = 1; i <= n; i++) {
total_paths += dp[mask][i];
}
}
}
cout << total_paths << endl;
return 0;
}
