#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

const int MAXN = 60;

const int M = 16;
const int INF = 1<<28;
int dp[1<<M][M], dpp[1<<M][M];
// 最短ハミルトンパス
int ShortestHamiltonPath(const vector<vector<int> > &g, int start){
    int n = g.size();
    int N = 1 << n;
    REP(S,N) REP(i,n) dp[S][i] = INF;
    dp[1<<start][start] = 0;
    REP(S,N) REP(i,n){
        if(!(S&(1<<i))) continue;
        REP(j,n){
            if(dp[S|(1<<j)][j] > dp[S][i] + g[i][j]){
                dp[S|(1<<j)][j] = dp[S][i] + g[i][j], dpp[S|(1<<j)][j] = i;
            }
        }
    }
    int t = min_element(dp[N-1], dp[N-1]+n) - dp[N-1];
    if(dp[N-1][t] == INF) return INF; // no route
    return dp[N-1][t];
}

bool check(const vector<vector<int> > &g, const vector<int> &v, int K){
    int n = v.size();
    vector<vector<int> > g2;
    g2.resize(n);
    REP(i,n) g2[i].resize(n,0);
    REP(i,n) REP(j,n){ // ノード番号を圧縮した隣接行列を生成
        g2[i][j] = g[v[i]][v[j]];
    }
    int w = ShortestHamiltonPath(g2, 0);
    return (w <= K);
}

int main(){
    int N,M,K;
    cin >> N >> M >> K;

    vector<vector<int> > g(N, vector<int>(N));
    REP(i,N){
        REP(j,N) g[i][j] = INF;
        g[i][i] = 0;
    }

    REP(i,M){
        int u,v;
        cin >> u >> v; u--;v--;
        g[u][v] = g[v][u] = 1;
    }

    REP(k,N) REP(i,N) REP(j,N){
        g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
    }
    vector<int> v;
    v.push_back(0);
    for(int i = N-1; i > 0; i--){
        if((int)v.size() == K+1) break;
        v.push_back(i);
        if(!check(g, v, K)){
            v.pop_back();
        }
    }
    ll res = 0;
    for(int i = 1; i < (int)v.size(); i++){
        res += (1LL << v[i]) - 1;
    }
    cout << res << endl;
    return 0;
}