#include <bits/stdc++.h>
using namespace std;
int n, m, K;
long long ans;
bool G[15][15];
vector<pair<int, int> > vec;
bool used[15], g[(1 << 6)][6];
int bel[15];
map<long long, bool> f;
long long gao(int *bel) {
  int mp[8] = {0}, now = 0;
  for (int i = 1; i <= n; i++)
    if (!mp[bel[i]]) mp[bel[i]] = now++;
  long long ret = 0;
  for (int i = 1; i <= n; i++) ret = ret * 6 + mp[bel[i]];
  return ret;
}
long long gao(vector<pair<int, int> > &vec) {
  int bel[15];
  for (int i = 0; i < vec.size(); i++)
    bel[vec[i].first] = bel[vec[i].second] = i;
  return gao(bel);
}
void calc() {
  int N = n / 2;
  memset(g, 0, sizeof(g));
  for (int i = 0; i < N; i++) g[1 << i][i] = G[vec[i].first][vec[i].second];
  for (int i = 1; i + 1 < (1 << N); i++)
    for (int j = 0; j < N; j++)
      if (g[i][j]) {
        int a = vec[j].first, b = vec[j].second;
        for (int k = 0; k < N; k++)
          if (!(i >> k & 1)) {
            int c = vec[k].first, d = vec[k].second;
            if ((G[a][c] && G[b][d]) || (G[a][d] && G[b][c]))
              g[i | (1 << k)][k] |= true;
          }
      }
  for (int i = 0; i < N; i++)
    if (g[(1 << N) - 1][i]) {
      f[gao(vec)] = true;
      return;
    }
  f[gao(vec)] = false;
}
void dfs1(int now) {
  if (now > n) {
    calc();
    return;
  }
  used[now] = true;
  for (int i = now + 1; i <= n; i++)
    if (!used[i]) {
      used[i] = true;
      vec.push_back(pair<int, int>(now, i));
      for (int j = 1;; j++)
        if (!used[j]) {
          dfs1(j);
          break;
        }
      used[i] = false;
      vec.pop_back();
    }
  used[now] = false;
}
bool dp(long long msk) {
  if (f.count(msk)) return f[msk];
  int bel[15], cnt[8] = {0}, mx = 0;
  long long mm = msk;
  for (int i = 0; i < n; i++, mm /= 6) {
    int x = mm % 6;
    bel[n - i] = x;
    cnt[x]++;
    mx = max(mx, x);
  }
  for (int i = 1; i <= n; i++)
    if (cnt[bel[i]] > 2) {
      int old = bel[i];
      for (int j = i + 1; j <= n; j++)
        if (bel[i] == bel[j]) {
          bel[i] = bel[j] = mx + 1;
          if (dp(gao(bel))) return f[msk] = true;
          bel[i] = bel[j] = old;
        }
      break;
    }
  return f[msk] = false;
}
void dfs2(int now, int a, int b) {
  if (now > n) {
    long long x = 1;
    for (int i = 0; i + 1 < a; i++) x *= K - i;
    if (dp(gao(bel))) ans += x;
    return;
  }
  bel[now] = a;
  for (int i = now + 1; i <= n; i++)
    if (!bel[i]) dfs2(i, a, b + 1);
  if (b % 2 == 0)
    for (int i = 1;; i++)
      if (!bel[i]) {
        dfs2(i, a + 1, 1);
        break;
      }
  bel[now] = 0;
}
int main() {
  scanf("%d%d%d", &n, &m, &K);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    G[x][y] = G[y][x] = true;
  }
  dfs1(1);
  dfs2(1, 1, 1);
  printf("%lld\n", ans);
  return 0;
}
