#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 13;
struct ts {
  int mask, l, r;
};
int n, m, k, step = 0;
ll ans;
int comp[N], comp_mask[N];
int cnk[N][N], f[N];
int g[N];
bool can_move[N][N];
int sz[(1 << N)];
int lst[(1 << N)][N];
int can[(1 << N)][N][N];
ts q[(1 << N) * N * N];
void init() {
  f[0] = cnk[0][0] = 1;
  for (int i = 1; i < N; ++i) {
    f[i] = f[i - 1] * i;
    cnk[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      cnk[i][j] = cnk[i - 1][j - 1] + cnk[i - 1][j];
    }
  }
  for (int i = 0; i < (1 << N); ++i) {
    for (int j = 0; j < N; ++j) {
      if ((i & (1 << j)) != 0) {
        lst[i][sz[i]++] = j;
      }
    }
  }
}
bool check(int y) {
  for (int i = 0; i < y; ++i) {
    comp_mask[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    comp_mask[comp[i]] |= (1 << i);
  }
  for (int i = 0; i < y; ++i) {
    assert(sz[comp_mask[i]] > 0);
    if (sz[comp_mask[i]] % 2 != 0) {
      return false;
    }
  }
  for (int i = 0; i < y; ++i) {
    bool found = false;
    for (int ll = 0; ll < sz[comp_mask[i]]; ++ll) {
      for (int rr = ll + 1; rr < sz[comp_mask[i]]; ++rr) {
        if (can_move[lst[comp_mask[i]][ll]][lst[comp_mask[i]][rr]]) {
          found = true;
          break;
        }
      }
      if (found) {
        break;
      }
    }
    if (!found) {
      return false;
    }
  }
  ++step;
  int qr = 0;
  for (int i = 0; i < n; ++i) {
    int msk = ((1 << n) - 1) ^ (1 << i);
    msk &= comp_mask[comp[i]];
    msk &= g[i];
    for (int jj = 0; jj < sz[msk]; ++jj) {
      if (n == 2) {
        return true;
      }
      int j = lst[msk][jj];
      if (can[(1 << i) | (1 << j)][i][j] != step) {
        can[(1 << i) | (1 << j)][i][j] = step;
        q[qr++] = {((1 << i) | (1 << j)), i, j};
      }
    }
  }
  while (qr > 0) {
    ts s = q[--qr];
    int left_neigs = (((1 << n) - 1) ^ s.mask) & g[s.l];
    for (int ii = 0; ii < sz[left_neigs]; ++ii) {
      int i = lst[left_neigs][ii];
      int right_neigs = (((1 << n) - 1) ^ s.mask ^ (1 << i)) & g[s.r];
      right_neigs &= comp_mask[comp[i]];
      for (int jj = 0; jj < sz[right_neigs]; ++jj) {
        int j = lst[right_neigs][jj];
        if (can[s.mask | (1 << i) | (1 << j)][i][j] != step) {
          can[s.mask | (1 << i) | (1 << j)][i][j] = step;
          q[qr++] = {(s.mask | (1 << i) | (1 << j)), i, j};
          if (q[qr - 1].mask == ((1 << n) - 1)) {
            return true;
          }
        }
      }
    }
  }
  return false;
}
void gen(int x, int y) {
  if (x >= n) {
    if (check(y)) {
      ans += cnk[k][y] * f[y];
    }
    return;
  }
  for (int i = 0; i < y; ++i) {
    comp[x] = i;
    gen(x + 1, y);
  }
  if (y + 1 <= min(n / 2, k)) {
    comp[x] = y;
    gen(x + 1, y + 1);
  }
}
void solve() {
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 0; i < n; ++i) {
    g[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      can_move[i][j] = false;
    }
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a;
    --b;
    g[a] |= (1 << b);
    g[b] |= (1 << a);
    can_move[a][b] = can_move[b][a] = true;
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        can_move[i][j] |= (can_move[i][k] & can_move[k][j]);
      }
    }
  }
  ans = 0;
  gen(0, 0);
  cout << ans << endl;
}
int main() {
  init();
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}
