import sequtils,strutils,math
var
    N,M,K,u,v : int
    D : array[1..60, array[1..60, int]]
(N, M, K) = stdin.readline.split.map(parseInt)

for i in 1..N:
    for j in 1..N:
        D[i][j] = 1000

for m in 1..M:
    (u,v) = stdin.readline.split.map(parseInt)
    D[u][v] = 1
    D[v][u] = 1

for k in 1..N:
    for i in 1..N:
        for j in 1..N:
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
var
    p : int
    Tezyuns : seq[seq[int]] = @[@[1,0]]
    T2 : seq[seq[int]]
    x : int
for n in countdown(N, 1):
    if D[1][n] <= K:
        T2 = @[]
        for tezyun in Tezyuns:
            var
                p = tezyun[^1]
            for i,t in tezyun[0..^2]:
                if i == tezyun.high - 1 and p + D[t][n] <= K:
                    T2.add(tezyun[0..i] & @[n,p + D[t][n]])
                else:
                    x = p + D[t][n] + D[n][tezyun[i + 1]] - D[t][tezyun[i + 1]]
                    if x <= K:
                        T2.add(tezyun[0..i] & @[n] & tezyun[(i + 1)..^2] & @[x])
        if T2.len > 0:
            Tezyuns = T2
var ans,ans1 : int64
for tezyun in Tezyuns:
    ans1 = 0
    for t in tezyun[0..^2]:
        ans1 += (1 shl (t - 1)) - 1
    ans = max(ans1,ans)
echo ans