import sys from collections import deque read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N, M, K = map(int, readline().split()) m = map(int, read().split()) G = [[] for _ in range(N)] for u, v in zip(m, m): u -= 1 v -= 1 G[u].append(v) G[v].append(u) def bfs(v): dist = [1000] * N q = deque([v]) dist[v] = 0 while q: v = q.popleft() for w in G[v]: if dist[w] != 1000: continue dist[w] = dist[v] + 1 q.append(w) return dist dist_mat = [bfs(v) for v in range(N)] def extract_subgraph(A): assert A[0] == 0 mat = [] for i in A: mat.append([dist_mat[i][j] for j in A]) return mat dp = [[K + 1] * (K + 1) for _ in range(1 << (K + 1))] def min_hamilton_path(A): mat = extract_subgraph(A) n = len(A) INF = K + 1 global dp dp[1][0] = 0 for s in range(3, 1 << n, 2): for i in range(n): dp[s][i] = INF if not (s & (1 << i)): continue t = s ^ (1 << i) x = INF for j in range(n): if not (t & (1 << j)): continue y = dp[t][j] + mat[i][j] if x > y: x = y dp[s][i] = x full = (1 << n) - 1 return min(dp[full]) A = [0] for n in range(N - 1, 0, -1): A.append(n) if min_hamilton_path(A) > K: A.pop() if len(A) == K + 1: break answer = sum((1 << x) - 1 for x in A) print(answer)