#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const double eps = 1e-6;
struct inout {
  static const int ibufl = 1 << 25;
  char in_buf[ibufl + 5], out_buf[ibufl + 5], *inf, *ouf;
  void init() {
    fread(in_buf, 1, ibufl, stdin);
    inf = in_buf;
    ouf = out_buf;
  }
  inout& operator>>(int& a) {
    int fh = 1;
    while (!(isdigit(*inf) || *inf == '-')) ++inf;
    if (*inf == '-') fh = -1, ++inf;
    a = 0;
    while (isdigit(*inf)) {
      a = a * 10 + *inf - '0';
      ++inf;
    }
    a *= fh;
    return *this;
  }
  inout& operator>>(char& a) {
    while (*inf == ' ' || *inf == '\n') ++inf;
    a = *inf;
    ++inf;
    return *this;
  }
  inout& operator>>(char* a) {
    while (*inf == ' ' || *inf == '\n') ++inf;
    while (!(*inf == ' ' || *inf == '\n')) {
      *a = *inf;
      ++inf;
      ++a;
    }
    *a = '\0';
    return *this;
  }
  inout& operator>>(double& a) {
    int fh = 1;
    double s;
    while (!(isdigit(*inf) || *inf == '-')) ++inf;
    if (*inf == '-') fh = -1, ++inf;
    a = 0;
    while (isdigit(*inf)) {
      a = a * 10 + *inf - '0';
      ++inf;
    }
    if (*inf == '.') {
      s = 0.1;
      ++inf;
      while (isdigit(*inf)) {
        a += s * (*inf - '0');
        ++inf;
        s *= 0.1;
      }
    }
    a *= fh;
    return *this;
  }
  void writeint(int x) {
    if (x / 10) writeint(x / 10);
    *ouf = x % 10 + '0';
    ++ouf;
  }
  inout& operator<<(int a) {
    if (a < 0) {
      *ouf = '-';
      ++ouf;
      a = -a;
    }
    writeint(a);
    return *this;
  }
  static const int sz = 2;
  inout& operator<<(char a) {
    *ouf = a;
    ++ouf;
    return *this;
  }
  inout& operator<<(char* a) {
    while (*a) {
      *ouf = *a;
      ++ouf;
      ++a;
    }
    return *this;
  }
  inout& operator<<(double a) {
    if (a < -eps) {
      *ouf = '-';
      ++ouf;
      a = -a;
    }
    writeint((int)a);
    a -= (int)a;
    *ouf = '.';
    ++ouf;
    for (int i = 1; i <= sz; i++) {
      a = a * 10;
      *ouf = (int)a + '0';
      ++ouf;
      a -= (int)a;
    }
    return *this;
  }
  void out() { fwrite(out_buf, 1, ouf - out_buf, stdout); }
};
inout io;
int num[15], n;
bool f[15][15];
int C[15], p[15][15], len[15];
pair<int, pair<int, int> > q[600000];
int t;
bool vis[1 << 12][14][15];
int tot;
inline bool dfs2(int mask, int x, int y) {
  q[++t] = make_pair(mask, make_pair(x, y));
  if (mask == (1 << n) - 1) return 1;
  for (int i = 1; i <= tot; i++) {
    for (int j = 1; j <= len[i]; j++)
      if (!(mask & (1 << p[i][j]))) {
        for (int K = j + 1; K <= len[i]; K++)
          if (!(mask & (1 << p[i][K]))) {
            if (f[p[i][j]][x] && f[p[i][K]][y] ||
                f[p[i][j]][y] && f[p[i][K]][x]) {
              if (!vis[mask | (1 << p[i][j]) | (1 << p[i][K])][p[i][j]]
                      [p[i][K]]) {
                vis[mask | (1 << p[i][j]) | (1 << p[i][K])][p[i][j]][p[i][K]] =
                    1;
                if (dfs2(mask | (1 << p[i][j]) | (1 << p[i][K]), p[i][j],
                         p[i][K]))
                  return 1;
              }
            }
          }
      }
  }
  return 0;
}
void dfs(int x, int used, int cnt) {
  if (x + cnt > n) return;
  if (x == n) {
    t = 0;
    tot = used;
    for (int i = 1; i <= used; i++) {
      for (int j = 1; j <= len[i]; j++) {
        for (int K = j + 1; K <= len[i]; K++)
          if (f[p[i][j]][p[i][K]]) {
            vis[(1 << p[i][j]) + (1 << p[i][K])][p[i][j]][p[i][K]] = 1;
            if (dfs2((1 << p[i][j]) + (1 << p[i][K]), p[i][j], p[i][K])) {
              for (int i = 1; i <= t; i++)
                vis[q[i].first][q[i].second.first][q[i].second.second] = 0;
              C[used]++;
              return;
            }
          }
      }
    }
    for (int i = 1; i <= t; i++)
      vis[q[i].first][q[i].second.first][q[i].second.second] = 0;
    return;
  }
  for (int i = 1; i <= used + 1; i++) {
    num[i]++;
    p[i][++len[i]] = x;
    dfs(x + 1, max(used, i), cnt + ((num[i] & 1) ? 1 : (-1)));
    num[i]--;
    --len[i];
  }
}
signed main() {
  io.init();
  int m, k;
  io >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int x, y;
    io >> x >> y;
    x--;
    y--;
    f[x][y] = f[y][x] = 1;
  }
  dfs(0, 0, 0);
  long long ans = 0;
  for (int i = 1; i <= k; i++) {
    long long p = 1;
    for (int j = k; j >= k - i + 1; j--) p *= j;
    ans += C[i] * p;
  }
  printf("%lld", ans);
  return 0;
}
