#include <fstream>
#include <vector>
using namespace std;
int main()
{ vector <vector <int> > b;// списки суміжності
          vector <int>  b0;// список суміжеості однієї вершини
  int nv,ne,m,             // вхідні дані з першого рядка
      c[2][9],             // довжина шляху
      i0=0,                // індекс того, що знаємо
      i1=1,                // індекс того, що обчислюємо
      j,k,l;               // лічильники
  ifstream fi;             // оголошення потоку зчтитування з файлу fi
  ofstream fo;             // оголошення потоку запису у файл fo
  fi.open("input.txt");    // прив'язування назви файлу до змінної fi
  fo.open("output.txt");   // gрив'язування назви файлу до змінної fo
  fi>>nv>>ne>>m;
  for (j=0; j<nv; j++) b.push_back(b0);
  for (l=0; l<ne; l++)
  { fi>>j>>k;
    b[j].push_back(k);
    b[k].push_back(j);
  }
  fi.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<b[j].size(); k++)
        c[i1][j]+=c[i0][b[j][k]];
    }
    i0=1-i0;
    i1=1-i1;
  }
  fo<<c[i0][nv-1]<<endl;
  fo.close();
  return 0;
}