import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Graph {
    int N;
    List<List<Integer>> graph;

    public Graph(int N) {
        this.N = N;
        graph = new ArrayList<>(N);
        for(int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }
    }
    public void addEdge(int a, int b) {
        graph.get(a).add(b);
        graph.get(b).add(a);
    }

    public int countNumberOfCycles(int lengthOfCycle) {
        int result = 0;
        boolean[] visited = new boolean[N];
        for(int i = 0; i < N; i++) {
            result += dfs(i, i, 1, lengthOfCycle, visited);
            visited[i] = true;
        }
    result /= 2;
        return result;
    }
    private int dfs(int node, int startingNodeOfCycle, int currentLengthOfCycle, int cycleLength, boolean[] visited) {
        if(currentLengthOfCycle == cycleLength) {
            for(int i = 0; i < graph.get(node).size(); i++) {
                if(graph.get(node).get(i) == startingNodeOfCycle) {
                    return 1;
                }
            }
            return 0;
        }

        visited[node] = true;
        int result = 0;
        for(int i = 0; i < graph.get(node).size(); i++) {
            int neighbour = graph.get(node).get(i);
            if(!visited[neighbour]) {
                result += dfs(neighbour, startingNodeOfCycle, currentLengthOfCycle + 1, cycleLength, visited);
            }
        }
        visited[node] = false;
        return result;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Graph g = new Graph(n);
        for(int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g.addEdge(a, b);
        }
        int cycleLength = sc.nextInt();
        System.out.println(g.countNumberOfCycles(cycleLength));
    }
}/*
5
6
0 1
0 2
1 2
2 3
2 4
3 4
3
*/