package work;
import java.util.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class Work
{ public static void main(String args[])
  { try 
    { int nv,ne,m, // вхідні дані з першого рядка
      i0=0,        // індекс того, що знаємо
      i1=1,        // індекс того, що обчислюємо
      j,k,l;       // лічильники
      int [][] c = new int [2][9];  // c[][j] - кількість маршрутів у вершину j
      FileReader in      = new FileReader( "input.txt");
      FileWriter out     = new FileWriter("output.txt");
      BufferedReader bin = new BufferedReader(in);
      Scanner          s = new Scanner(bin);
      LinkedList b = new LinkedList();// списки суміжності
      nv = s.nextInt();
      ne = s.nextInt();
      m  = s.nextInt();
      for (j=0; j<nv; j++) b.add(new LinkedList());
      for (l=0; l<ne; l++)
      { j = s.nextInt();
        k = s.nextInt();
        ((LinkedList) b.get(j)).add(k);
        ((LinkedList) b.get(k)).add(j);
      }
      in.close();
      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<((LinkedList) b.get(j)).size(); k++)
            c[i1][j]+=c[i0][ (int) ((LinkedList) ((LinkedList) b.get(j))).get(k)];
        }
        i0=1-i0;
        i1=1-i1;
      }
      out.write(c[i0][nv-1]+"\n");
      out.close();
    }
    catch (IOException e) {}
  }
}