#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
#pragma GCC target("avx", "avx2")
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
const int N = 12;
bool mp[N][N];
int n, m, K;
int be[N], num[7];
int vis[1 << N][N][N], ok[1 << N][N][N], tag;
bool dfs(int mask, int u, int v) {
  if (!mask) return 1;
  if (vis[mask][u][v] == tag) return ok[mask][u][v];
  vis[mask][u][v] = tag;
  for (int i = 0; i <= n - 1; i++)
    if ((mask >> i & 1)) {
      for (int j = i + 1; j <= n - 1; j++)
        if (i != j && (mask >> j & 1) && be[i] == be[j]) {
          if (!(mp[u][i] && mp[v][j]) && !(mp[u][j] && mp[v][i])) continue;
          if (dfs(mask ^ (1 << i) ^ (1 << j), i, j)) return ok[mask][u][v] = 1;
        }
    }
  return ok[mask][u][v] = 0;
}
bool chk(int k) {
  int mask = (1 << n) - 1;
  for (int i = 0; i <= n - 1; i++) {
    for (int j = i + 1; j <= n - 1; j++) {
      ++tag;
      if (mp[i][j] && be[i] == be[j] && dfs(mask ^ (1 << i) ^ (1 << j), i, j)) {
        return 1;
      }
    }
  }
  return 0;
}
long long ans = 0;
void dfs(int u, int k) {
  if (u == n) {
    bool ok = 1;
    for (int i = 1; i <= k; i++) ok &= ~num[i] & 1;
    if (!ok) return;
    if (chk(k)) {
      long long cf = 1;
      for (int i = K; i >= K - k + 1; i--) cf *= i;
      ans += cf;
    }
    return;
  }
  for (int i = 1; i <= min(6, k + 1); i++) {
    be[u] = i, num[i]++;
    dfs(u + 1, max(k, i));
    be[u] = 0, num[i]--;
  }
}
bool _[N];
int ah = 0;
void d(int u) {
  _[u] = 1, ah++;
  for (int i = 0; i < n; i++)
    if (!_[i] && mp[u][i]) {
      d(i);
    }
}
int main() {
  n = read(), m = read(), K = read();
  for (int i = 1; i <= m; i++) {
    int u = read() - 1, v = read() - 1;
    mp[u][v] = mp[v][u] = 1;
  }
  d(0);
  if (ah != n) return puts("0"), 0;
  dfs(0, 0);
  print(ans, '\n');
  return 0;
}
