#ifdef KOMAKI_LOCAL #include #else #define NDEBUG #endif #include #include #include using namespace std; #define i64 int64_t #define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i) #define sz(v) ((i64)((v).size())) #define bit(n) (((i64)1)<<((i64)(n))) #define all(v) (v).begin(), (v).end() template void deploy(std::ostream &os, const TUPLE &tuple){} template void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get(t); deploy(os, t); } template std::ostream& operator<<(std::ostream &os, const std::tuple &t){ os << "("; deploy<0, std::tuple, Ts...>(os, t); os << ")"; return os; } template std::ostream& operator<<(std::ostream &os, std::vector &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::set &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::queue &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::priority_queue &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::pair &p){ os << "(" << p.first << ", " << p.second << ")"; return os; } template std::ostream& operator<<(std::ostream &os, std::map &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } template std::ostream& operator<<(std::ostream &os, std::unordered_map &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } #define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; } #define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; } #define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; } #define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; } #define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; } #define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; } #define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; } const i64 MAX = 64; const i64 K = 15; const i64 BIT_K = bit(K); int visited[K + 1][K][BIT_K]; int main() { int distances[MAX][MAX]; rep(i, MAX)rep(j, MAX) distances[i][j] = i == j ? 0 : K; i64 n, m, k; cin >> n >> m >> k; rep(i, m){ i64 u, v; cin >> u >> v; distances[u - 1][v - 1] = 1; distances[v - 1][u - 1] = 1; } rep(mid, n)rep(i, n)rep(j, n) distances[i][j] = min(distances[i][j], distances[i][mid] + distances[mid][j]); i64 best_mask = 0; for(i64 t = n - 1; 0 <= t && __builtin_popcountll(best_mask) < k; --t){ i64 next_mask = best_mask | bit(t); i64 size = 0; int terminals[K]; rep(i, n)if(next_mask & bit(i)) terminals[size++] = i; memset(visited, 0, sizeof(visited)); rep(i, size){ int d = distances[0][terminals[i]]; if(d <= K) visited[d][i][bit(i)] = bit(0); } for(int step = 0; step < k && best_mask != next_mask; ++step){ for(int tail = 0; tail < size && best_mask != next_mask; ++tail){ int *v = visited[step][tail]; for(int mask = 0; mask < bit(size); ++mask){ if(v[mask] != bit(0)) continue; for(int s = step; s < k; ++s) visited[s][tail][mask] = bit(1); for(int adj = 0; adj < size; ++adj){ int d = step + distances[terminals[tail]][terminals[adj]]; if(d <= K){ visited[d][adj][mask | bit(adj)] |= bit(0); } } } } } for(int step = 0; step <= k; ++step){ for(int tail = 0; tail < size; ++tail){ if(visited[step][tail][bit(size) - 1]) best_mask = next_mask; } } } i64 ans = 0; rep(i, n)if(best_mask & bit(i)) ans += bit(i) - 1; cout << ans << endl; }