#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//と思ったら僕がバカでしたごめんなさいリバーシのルールを忘れていましたごめんなさい


int wf[60][60];
int dp[16][1<<16];
int tsp(vector<int> u){
	for(int i = 0 ; i < u.size() ; i++)
		for(int j = 0 ; j < (1<<u.size()) ; j++)
			dp[i][j] = 1e9;
	for(int i = 0 ; i < u.size() ; i++)
		dp[i][(1<<i)] = wf[0][u[i]];
	
	for(int i = 0 ; i < (1<<u.size()) ; i++)
		for(int j = 0 ; j < u.size() ; j++)
			for(int k = 0 ; k < u.size() ; k++)
				if( i>>j & 1 ) dp[k][i|(1<<k)] = min(dp[k][i|(1<<k)],dp[j][i]+wf[u[j]][u[k]]);
	int res = 1e9;
	for(int i = 0 ; i < u.size() ; i++)
		res = min(res,dp[i][(1<<u.size())-1]);
	return res;
}
int main(){
	for(int i = 0 ; i < 60 ; i++)
		for(int j = 0 ; j < 60 ; j++)
			wf[i][j] = i==j?0:1e9;
	int N,M,K;
	cin >> N >> M >> K;
	for(int i = 0 ; i < M ; i++){
		int a,b;
		cin >> a >> b;
		a--,b--;
		wf[a][b] = wf[b][a] = 1;
	}
	for(int i = 0 ; i < 60 ; i++)
		for(int j = 0 ; j < 60 ; j++)
			for(int k = 0 ; k < 60 ; k++)
				wf[j][k] = min(wf[j][i]+wf[i][k],wf[j][k]);
	
	
	vector<int> go;
	
	long long res = 0;
	for(int i = N - 1 ; i >= 0 ; i--){
		go.push_back(i);
		if( tsp(go) <= K ){
			res += (1ll<<i) - 1;
		}else go.pop_back();
	}
	cout << res << endl;
}