f=open("input.txt","r")
[nv,ne,m]=f.readline().split() 
nv=int(nv)  # кількість вершин
ne=int(ne)  # кількість ребер
m =int(m)   # довжина маршруту
b=[]        # списки суміжності
for k in range(nv):
  b.append([])
for l in range(ne):
  [j, k]=f.readline().split()
  j=int(j)
  k=int(k)
  b[j].append(k)
  b[k].append(j)
f.close
c=[[0]*nv, [0]*nv]
c[0][0]=1
i0=0  # індекс того, що знаємо
i1=1  # індекс того, що обчислюємо
for l in range(m):
  c[i1]=[0]*nv  
  for j in range(nv):
    for k in range(len(b[j])):
       c[i1][j]+=c[i0][b[j][k]] 
  i0=1-i0
  i1=1-i1
f = open("output.txt","w")
f.write(str(c[i0][nv-1]) + '\n')
f.close()