import sys
input = sys.stdin.readline

def solve():
    N, M, K = map(int, input().split())
    INF = 10**9

    # --- Floyd-Warshall 用行列 ---
    dist = [[INF]*N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        dist[a][b] = dist[b][a] = 1

    # --- 全点間最短距離 ---
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            di = dist[i]
            via = di[k]
            if via == INF:
                continue
            for j in range(N):
                nd = via + dk[j]
                if nd < di[j]:
                    di[j] = nd

    # --- 高い番号から貪欲に採用 ---
    V = [0]  # 必ず 0 番（頂点1）は入れておく
    score = 0

    for i in range(N-1, 0, -1):
        if len(V) >= K+1:
            break

        V.append(i)

        # bitDP: V の全頂点を巡回する最短距離
        L = len(V)
        dp = [[10**9]*L for _ in range(1 << L)]
        dp[1][0] = 0  # 最初は V[0]（頂点1）から開始

        for mask in range(1, 1 << L):
            for x in range(L):
                if not (mask & (1 << x)):
                    continue
                dpx = dp[mask][x]
                if dpx >= 10**9:
                    continue
                for y in range(L):
                    if mask & (1 << y):
                        continue
                    dp[mask | (1 << y)][y] = min(
                        dp[mask | (1 << y)][y],
                        dpx + dist[V[x]][V[y]]
                    )

        full = (1 << L) - 1
        ok = any(dp[full][j] <= K for j in range(L))

        if ok:
            score += (1 << i) - 1
        else:
            V.pop()

    print(score)


if __name__ == "__main__":
    solve()