#include <bits/stdc++.h>
using namespace std;
const int N = 25;
const double eps = 1e-10;
int n, m, k, u, v;
vector<int> g[N];
struct mat {
  int a[N][N];
  mat() {}
  void clear() { memset(a, 0, sizeof a); }
} a;
inline long long Gao(mat A, int n) {
  static int a[N][N];
  long long ans = 1;
  memcpy(a, A.a, sizeof A.a);
  --n;
  for (int i = 1; i <= n; ++i) {
    int t = -1;
    for (int j = i; j <= n; ++j)
      if (a[j][i]) {
        t = j;
        break;
      }
    if (t < 0) return 0;
    if (t != i) swap(a[i], a[t]), ans *= -1;
    for (int j = i + 1; j <= n; ++j) {
      while (a[j][i]) {
        int md = a[i][i] / a[j][i];
        for (int k = i; k <= n; ++k) a[i][k] -= md * a[j][k];
        swap(a[i], a[j]);
        ans *= -1;
      }
    }
    ans *= a[i][i];
  }
  return ans;
}
namespace solver {
int id[N];
long long f[N];
inline void put() {
  static long long C[N][N], ans = 0;
  for (int i = 1; i <= n; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  }
  for (int i = k; i <= n; ++i) {
    if ((i - k) & 1)
      ans -= C[i][k] * f[i];
    else
      ans += C[i][k] * f[i];
  }
  printf("%lld\n", ans);
}
void main() {
  for (int used = 0; used < (1 << n); ++used) {
    int idx = 0, ans = 1;
    for (int i = 0; i < n; ++i)
      if (used >> i & 1) id[i] = ++idx;
    a.clear();
    for (int i = 0; i < n; ++i) {
      if (used >> i & 1) {
        for (auto v : g[i])
          if (used >> v & 1) {
            a.a[id[i]][id[v]] = -1;
            ++a.a[id[i]][id[i]];
          }
      } else {
        int tot = 0;
        for (auto v : g[i])
          if (used >> v & 1) ++tot;
        ans *= tot;
      }
    }
    f[n - idx] += (long long)ans * Gao(a, idx);
  }
  put();
}
}  // namespace solver
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &u, &v);
    --u, --v;
    g[u].push_back(v), g[v].push_back(u);
  }
  solver ::main();
  return 0;
}
