def solve():
    N, M, K = map(int, input().split())

    es = [set() for _ in range(N)]

    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        es[u].add(v)
        es[v].add(u)

    dp = {}

    def rec(p, c, k):
        pck = (p, c, k)

        if k == 0:
            return c

        if pck in dp:
            return dp[pck]

        ma = 0
        for n in es[p]:
            ma = max(ma, rec(n, c | (1 << n), k - 1))

        dp[pck] = ma
        return ma

    ab = rec(0, 0, K)

    ans = 0
    for i in range(N):
        if ab & 1 == 1:
            ans += 2 ** i - 1
        ab >>= 1

    print(ans)


if __name__ == '__main__':
    solve()