#include<bits/stdc++.h> #define fi first #define se second #define FOR(i, k, n) for(int i = k; i <= n; i++) #define FOR1(i, k, n) for(int i = k; i >= n; i--) #define pb push_back #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define vi vector<int> #define pii pair<int, int> #define vii vector<pii> #define ll long long #define vll vector<ll> #define pll pair<ll, ll> #define re return 0 #define mii map<int, int> #define input "ALONE.inp" #define output "ALONE.out" #define rf freopen(input, "r", stdin); freopen(output, "w", stdout) using namespace std; const int maxn = 3e5 + 5; const int mod = 1e9 + 7; const int base = 998244353; const int base1 = 31; const int SZ = 320; const ll INF = 1e18; void add(int &a, int b) { a += b; if(a >= mod) a -= mod; if(a < 0) a += mod; } mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return uniform_int_distribution<int>(l, r) (rd); } ll dp[maxn][50]; vi adj[maxn]; int a[maxn]; bool cmp(int x, int y) { return __builtin_popcount(x) < __builtin_popcount(y); } int main() { fastio; int n, m, k; cin >> n >> m >> k; FOR(i, 1, n) cin >> a[i], a[i]--; FOR(i, 1, m) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } FOR(i, 1, n) dp[i][(1 << a[i])] = 1; vi vv; FOR(mask, 1, (1 << k) - 1) vv.pb(mask); sort(vv.begin(), vv.end(), cmp); for(auto mask : vv) { FOR(u, 1, n) { for(auto v : adj[u]) { if((mask >> a[v]) & 1) continue; dp[v][mask ^ (1 << a[v])] += dp[u][mask]; } } } ll ans = 0; FOR(i, 1, n) FOR(mask, 0, (1 << k) - 1) { if(__builtin_popcount(mask) <= 1) continue; ans += dp[i][mask]; } cout << ans; re; }