using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
class Example
{ public static void Main()
  { try 
    { int nv,ne,m, // вхідні дані з першого рядка
      i0=0,        // індекс того, що знаємо
      i1=1,        // індекс того, що обчислюємо
      j,k,l;       // лічильники
      int [,] c = new int [2,9];  // c[,j] - кількість маршрутів у вершину j
      using (StreamReader file = new StreamReader("input.txt"))
      { string[] s = file.ReadLine().Split(' ');
        nv = Int32.Parse(s[0]);
        ne = Int32.Parse(s[1]);
        m  = Int32.Parse(s[2]);
        List<List<int>> b = new List<List<int>>();// списки суміжності
        for (j=0; j<nv; j++) b.Add(new List<int>());
        for (l=0; l<ne; l++)
        { s = file.ReadLine().Split(' ');
          j = Int32.Parse(s[0]);
          k = Int32.Parse(s[1]);
          b[j].Add(k);
          b[k].Add(j);
        }
        for (j=0; j<nv; j++) c[i0,j]=0;
        c[i0,0]=1;
        for (l=0; l<m; l++)
        { for (j=0; j<nv; j++)
          { c[i1,j]=0;
            for (k=0; k< b[j].Count; k++) c[i1,j]+=c[i0, b[j][k]];
          }
          i0=1-i0;
          i1=1-i1;
        }
        File.WriteAllText ("output.txt", Convert.ToString(c[i0,nv-1])); 
      }
    }
    catch (Exception e) {Console.WriteLine(e.Message);}
  }
}