#include <bits/stdc++.h>
using namespace std;
const int N = 12;
const int M = N + 7;
const double EPS = 1e-10;
const int MOD = 1e9 + 7;
const long long INF = 2e18;
bool edge[M][M];
map<long long, bool> dp;
void calcDP(int n, vector<int>& col) {
  auto i = find(col.begin(), col.end(), -1) - col.begin();
  if (i == (int)col.size()) {
    int pos[n][2];
    for (int i = 0; i < (int)col.size(); i++) {
      pos[col[i]][0] = pos[col[i]][1];
      pos[col[i]][1] = i;
    }
    vector<vector<int>> d(1 << n, vector<int>(n));
    for (int i = 0; i < n; i++)
      if (edge[pos[i][0]][pos[i][1]]) d[1 << i][i] = true;
    for (int mask = 0; mask < (1 << n); mask++) {
      for (int i = 0; i < n; i++) {
        if (!d[mask][i]) continue;
        for (int j = 0; j < n; j++) {
          if (!((mask >> j) & 1)) {
            d[mask | (1 << j)][j] |=
                edge[pos[j][0]][pos[i][0]] && edge[pos[j][1]][pos[i][1]];
            d[mask | (1 << j)][j] |=
                edge[pos[j][0]][pos[i][1]] && edge[pos[j][1]][pos[i][0]];
          }
        }
      }
    }
    for (int i = 0; i < n; i++) {
      if (d[(1 << n) - 1][i]) {
        long long hash = 0;
        for (int c : col) hash = hash * 6 + c;
        dp[hash] = true;
        break;
      }
    }
    return;
  }
  for (int j = i + 1; j < (int)col.size(); j++) {
    if (col[j] == -1) {
      col[i] = col[j] = n;
      calcDP(n + 1, col);
      col[i] = col[j] = -1;
    }
  }
}
bool calcAdvancedDP(vector<int> col) {
  vector<int> p((int)col.size(), -1);
  int cnt = 0;
  for (int i = 0; i < (int)col.size(); i++)
    if (p[col[i]] == -1) p[col[i]] = cnt++;
  vector<int> count(cnt, 0);
  long long hash = 0;
  for (int i = 0; i < (int)col.size(); i++) {
    col[i] = p[col[i]];
    count[col[i]]++;
    hash = hash * 6 + col[i];
  }
  if (dp.count(hash)) return dp[hash];
  bool res = false;
  for (int i = 0; i < (int)col.size(); i++) {
    if (count[col[i]] <= 2) continue;
    for (int j = i + 1; j < (int)col.size() && !res; j++) {
      if (col[i] != col[j]) continue;
      int old = col[i];
      col[i] = col[j] = cnt;
      res |= calcAdvancedDP(col);
      col[i] = col[j] = old;
    }
    break;
  }
  return dp[hash] = res;
}
void calcAdvancedDP(int n, vector<int>& col) {
  int i = find(col.begin(), col.end(), -1) - col.begin();
  if (i == (int)col.size()) {
    calcAdvancedDP(col);
    return;
  }
  for (int x = 0; x <= n; x++) {
    for (int j = i + 1; j < (int)col.size(); j++) {
      if (col[j] == -1) {
        col[i] = col[j] = x;
        calcAdvancedDP(x == n ? x + 1 : n, col);
        col[i] = col[j] = -1;
      }
    }
  }
}
void solve() {
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int v, u;
    scanf("%d %d", &v, &u);
    v--;
    u--;
    edge[v][u] = edge[u][v] = true;
  }
  vector<int> col(n, -1);
  calcDP(0, col);
  calcAdvancedDP(0, col);
  vector<long long> fact(k + 1);
  fact[0] = 1;
  for (int i = 1; i <= k; i++) fact[i] = fact[i - 1] * i;
  long long ans = 0;
  for (auto cur : dp) {
    if (!cur.second) continue;
    long long hash = cur.first;
    int colors = 0;
    while (hash) {
      colors = max(colors, (int)(hash % 6));
      hash /= 6;
    }
    if (colors + 1 <= k) ans += fact[k] / fact[k - colors - 1];
  }
  printf("%lld\n", ans);
}
int main() {
  int tt = 1;
  while (tt--) {
    solve();
  }
  return 0;
}
