/*
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,abm,fma,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define pb(a) push_back(a)
#define mt make_tuple
const ll INF = 0x3f3f3f3f;
const ll inf =  1e9;
ll modulo = pow(10,9) + 7;

ll getmin(vector<int>& arr, vector<vector<int> >& dt){
      ll n = arr.size();
      vector<vector<int> > dp(1<<n, vector<int>(n, inf));
      dp[(1<<0)][0] = 0;
      for(int i =  0 ; i<(1<<n); i++){
            for(int j = 0; j<n; j++){
                  if((1<<j) & i){
                        for(int k = 0; k<n; k++){
                              if(!((1<<k) & i)){
                                    int bt = (i^(1<<k));
                                    dp[bt][k] = min(dp[bt][k], dp[i][j] + dt[arr[j]][arr[k]]);
                              }
                        }
                  }
            }
      }
      int mn = inf;
      fori(n){
            mn = min(mn, dp[((1<<n)-1)][i]);
      }
      return mn;
}

void deal(){
      ll n, m, k;
      cin>>n>>m>>k;
      vector<vector<int> > g(n);
      vector<vector<int> > dt(n, vector<int>(n, inf));
      fori(n){
            dt[i][i] = 0;
      }
      fori(m){
            ll ai, bi;
            cin>>ai>>bi;
            --ai, --bi;
            g[ai].pb(bi);
            g[bi].pb(ai);
            dt[ai][bi] = 1;
            dt[bi][ai] = 1;
      }
      forj(n){
            fori(n){
                  fork(n){
                        dt[i][k] = min(dt[i][k], dt[i][j] + dt[j][k]);
                  }
            }
      }
      vector<int> all({0});
      ll ans = 0;
      for(ll i = n-1; i ; i--){
            auto cur = all;
            cur.pb(i);
            if(getmin(cur, dt) <= k){
                  all = cur;
                  ans += (1ll << i) - 1;
            }
            if(all.size() == k+1){
                  break;
            }
      }
      cout<<ans;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    deal();
}