f = File.open("input.txt","r")
(nv, ne, m)=f.readline.split
nv=nv.to_i  # кількість вершин
ne=ne.to_i  # кількість ребер
m = m.to_i  # довжина маршруту
b=[]        # списки суміжності
for k in 0...nv
  b[k]=[]
end
for l in 0...ne
  (j, k)=f.readline.split
  j=j.to_i
  k=k.to_i
  b[j].push(k)
  b[k].push(j)
end
f.close
c=[[0]*nv, [0]*nv]
c[0][0]=1
i0=0  # індекс того, що знаємо
i1=1  # індекс того, що обчислюємо
for l in 0...m
  c[i1]=[0]*nv  
  for j in 0...nv
    for k in 0...b[j].length
       c[i1][j]+=c[i0][b[j][k]]
    end
  end 
  i0=1-i0
  i1=1-i1
end
f = File.open("output.txt","w")
f.puts c[i0][nv-1]
f.close