#include <bits/stdc++.h>
using namespace std;
const int N = 12;
const int M = 1 << 12;
const long long P = 998244353LL;
int n, m, k, cnt[M];
long long fac[N << 1], ans = 0, bin[N];
bool e[N][N], f[M][N];
map<long long, bool> ok;
vector<int> g, bel;
namespace Fread {
const int L = 1 << 15;
char buffer[L], *S, *T;
inline char Getchar() {
  if (S == T) {
    T = (S = buffer) + fread(buffer, 1, L, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
template <class T>
inline void read(T &X) {
  char ch;
  T op = 1;
  for (ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar())
    if (ch == '-') op = -1;
  for (X = 0; ch >= '0' && ch <= '9'; ch = Getchar())
    X = (X << 1) + (X << 3) + ch - '0';
  X *= op;
}
}  // namespace Fread
using Fread::read;
inline int lowbit(int s) { return s & (-s); }
inline long long getDivHash() {
  vector<int> tmp(n);
  long long res = 0;
  for (int i = 0; i < g.size(); i++) {
    for (int j = 0; j < n; j++) {
      if (!(g[i] & (1 << j))) continue;
      tmp[j] = i;
    }
  }
  for (int i = 0; i < n; i++) res += bin[i] * tmp[i];
  return res;
}
inline long long getPairHash(vector<int> &v) {
  long long res = 0;
  for (int i = 0; i < n; i++) {
    assert(v[i] != -1);
    res += bin[i] * v[i];
  }
  return res;
}
inline long long maintain(vector<int> cur) {
  int p = 0;
  vector<int> flag(n, -1);
  for (int i = 0; i < cur.size(); i++) {
    if (flag[cur[i]] == -1) flag[cur[i]] = p++;
    cur[i] = flag[cur[i]];
  }
  return getPairHash(cur);
}
bool dp(long long cur) {
  if (ok.find(cur) != ok.end()) return ok[cur];
  long long res = false;
  vector<int> tmp(n);
  long long t = cur;
  for (int i = 0; i < n; i++) {
    tmp[i] = t % 6;
    t /= 6;
  }
  int tot = n / 2;
  vector<int> valCnt(tot);
  for (int i = 0; i < n; i++) ++valCnt[tmp[i]];
  for (int i = 0; i < n; i++) {
    if (valCnt[tmp[i]] <= 2) continue;
    int oldVal = tmp[i];
    for (int j = i + 1; j < n; j++) {
      if (tmp[j] != tmp[i]) continue;
      tmp[i] = tmp[j] = tot;
      if (dp(maintain(tmp))) {
        res = true;
        break;
      }
      tmp[i] = tmp[j] = oldVal;
    }
    break;
  }
  ok[cur] = res;
  return res;
}
inline bool chkDiv() {
  long long cur = getDivHash();
  return dp(cur);
}
inline void chkPair() {
  int tot = n / 2;
  vector<int> p1(tot, -1), p2(tot, -1);
  for (int i = 0; i < n; i++) {
    if (p1[bel[i]] == -1) {
      p1[bel[i]] = i;
    } else {
      assert(p2[bel[i]] == -1);
      p2[bel[i]] = i;
    }
  }
  for (int s = 0; s < (1 << tot); s++)
    for (int i = 0; i < tot; i++) f[s][i] = 0;
  for (int i = 0; i < tot; i++) f[1 << i][i] = 1;
  for (int s = 1; s < (1 << tot); s++) {
    for (int i = 0; i < tot; i++) {
      if (!(s & (1 << i))) continue;
      if (!f[s][i]) continue;
      int x1 = p1[i], y1 = p2[i];
      for (int j = 0; j < tot; j++) {
        if (s & (1 << j)) continue;
        int x2 = p1[j], y2 = p2[j];
        if ((e[x1][x2] && e[y1][y2]) || (e[x1][y2] && e[x2][y1])) {
          f[s ^ (1 << j)][j] = 1;
        }
      }
    }
  }
  long long cur = getPairHash(bel);
  bool res = false;
  for (int i = 0; i < tot; i++) {
    if (!f[(1 << tot) - 1][i]) continue;
    if (e[p1[i]][p2[i]]) {
      res = true;
      break;
    }
  }
  ok[cur] = res;
}
void dfsPair(int s, int cur) {
  if (s == (1 << n) - 1) {
    chkPair();
    return;
  }
  int p = 0;
  for (int i = 0; i < n; i++) {
    if (!(s & (1 << i))) {
      p = i;
      break;
    }
  }
  for (int i = p + 1; i < n; i++) {
    if (s & (1 << i)) continue;
    bel[p] = bel[i] = cur;
    int tos = s ^ (1 << p) ^ (1 << i);
    dfsPair(tos, cur + 1);
    bel[p] = bel[i] = -1;
  }
}
void dfsDiv(int s) {
  if (s == (1 << n) - 1) {
    if (chkDiv()) {
      if (g.size() <= k) {
        long long res = fac[k] / fac[k - g.size()];
        ans += res;
      }
    }
    return;
  }
  int r = ((1 << n) - 1) ^ s, x = lowbit(r);
  for (int sub = r; sub; sub = (sub - 1) & r) {
    if (!(sub & x)) continue;
    if (cnt[sub] & 1) continue;
    g.emplace_back(sub);
    dfsDiv(s ^ sub);
    g.pop_back();
  }
}
int main() {
  read(n), read(m), read(k);
  fac[0] = 1;
  for (int i = 1; i <= k; i++) fac[i] = fac[i - 1] * i;
  for (int s = 0; s < (1 << n); s++) cnt[s] = __builtin_popcount(s);
  bin[0] = 1;
  for (int i = 1; i < n; i++) bin[i] = bin[i - 1] * 6;
  for (int x, y, i = 1; i <= m; i++) {
    read(x), read(y);
    x--, y--;
    e[x][y] = e[y][x] = 1;
  }
  bel.resize(n, -1);
  dfsPair(0, 0);
  dfsDiv(0);
  printf("%lld\n", ans);
  return 0;
}
