import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int nodes = sc.nextInt();
        int edges = sc.nextInt();
        List<Set<Integer>> adjacencyList = new ArrayList<>();

        for (int i = 0; i < nodes; i++) {
            adjacencyList.add(new HashSet<>());
        }

        for (int i = 0; i < edges; i++) {
            int node1 = sc.nextInt();
            int node2 = sc.nextInt();
            adjacencyList.get(node1).add(node2);
            adjacencyList.get(node2).add(node1);
        }

        int targetActiveNodes = sc.nextInt();
        boolean[] currentActiveNodes = new boolean[nodes];
        Arrays.fill(currentActiveNodes, true);
        int activeNodeCount = nodes;
        int days = 1;

        while (activeNodeCount < targetActiveNodes) {
            boolean[] nextActiveNodes = new boolean[nodes];
            for (int i = 0; i < nodes; i++) {
                int activeNeighbors = 0;
                for (int neighbor : adjacencyList.get(i)) {
                    if (currentActiveNodes[neighbor]) activeNeighbors++;
                }

                if (currentActiveNodes[i] && activeNeighbors == 3) {
                    nextActiveNodes[i] = true;
                } else if (!currentActiveNodes[i] && activeNeighbors < 3) {
                    nextActiveNodes[i] = true;
                }
            }

            currentActiveNodes = nextActiveNodes;
            activeNodeCount = 0;
            for (boolean isActive : currentActiveNodes) {
                if (isActive) activeNodeCount++;
            }
            days++;
        }

        System.out.println(days);
    }
}