#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef _MSC_VER #include #endif #define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i) #define rep(i, n) FOR(i, 0, n) #define ALL(v) v.begin(), v.end() #define REV(v) v.rbegin(), v.rend() #define MEMSET(v, s) memset(v, s, sizeof(v)) #define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end()) #define MP make_pair #define MT make_tuple using namespace std; typedef long long ll; typedef pair P; const int N = 65; vector G[N]; int d[N][N]; int num[N]; int dp[N][1 << 15]; int idx; int n, m, k; int rec(int pos, int x){ if (!x) return 0; int &res = dp[pos][x]; if (res + 1) return res; res = 1e9; rep(i, n){ int nx = x; if (num[i] >= 0 && (x >> num[i] & 1)){ nx &= ~(1 << num[i]); res = min(res, d[pos][i] + rec(i, nx)); } } return res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m >> k; rep(i, N) rep(j, N) if (i != j) d[i][j] = 1e9; rep(i, m){ int u, v; cin >> u >> v; --u, --v; d[u][v] = d[v][u] = 1; G[u].push_back(v); G[v].push_back(u); } rep(i, n) rep(j, n) rep(k, n) d[j][k] = min(d[j][k], d[j][i] + d[i][k]); int st = -1; for (int i = n - 1; i >= 0; --i){ if (d[0][i] <= k){ st = i; break; } } ll ans = (1ll << st) - 1; idx = 1; MEMSET(num, -1); num[st] = 0; for (int i = st - 1; i >= 1; --i){ MEMSET(dp, -1); num[i] = idx; int dist = rec(0, (1 << idx + 1) - 1); //cout << dist << endl; if (dist <= k){ ++idx; ans += (1ll << i) - 1; } else{ num[i] = -1; } } cout << ans << endl; return 0; }