#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class graph {
public:
  graph(int count)
    : _paths(0)
    , _accessibility(count)
  {
    for (int i = 0; i < count; i++) {
      _accessibility.push_back(vector<bool>(count));
      _accessibility[i].resize(count);
      fill(_accessibility[i].begin(), _accessibility[i].end(), false);
    }

    _used.resize(count);
    fill(_used.begin(), _used.end(), false);
  }

  void add_edge(int a, int b) {
    _accessibility[a][b] = true;
  }

  int paths() const {
    return _paths;
  }

  void find_paths(int from, int to, int days, int indent = 0) {
    _used[from] = true;
    if (from == to && days >= 0) {
      ++_paths;
      _used[from] = false;
      return;
    }

    if (days == 0) {
      if (from == to) {
        ++_paths;
      }
      _used[from] = false;
      return;
    }

    for (int i = 0; i < _accessibility[from].size(); ++i)
      if (_accessibility[from][i] && !_used[i]) {
        find_paths(i, to, days - 1, indent + 2);
      }
    _used[from] = false;
  }

private:
  int _paths;
  vector< vector<bool> > _accessibility;
  vector< bool > _used;
 };

int main () {
  int tourbase_count;
  int edges_count;
  int point_a, point_b;
  int max_days;

  cin >> tourbase_count;
  cin >> edges_count;

  cin >> point_a >> point_b;
  cin >> max_days;

  graph graph(tourbase_count);

  for (int i = 0; i < edges_count; i++) {
    int a, b;
    cin >> a >> b;
    graph.add_edge(a - 1, b - 1);
  }

  graph.find_paths(point_a - 1, point_b - 1, max_days);

  cout << graph.paths() << endl;

  return 0;
 }