Induced subgraphs P12120

Given an undirected graph G = (V, E), any S ⊆ V induces a subgraph G[S] = (S, E′), where E′ contains all edges in E that join two vertices in S. Let d(S) denote the minimum degree of the vertices in G[S].

You are given a graph G and a size s. Which is the maximum degree d for which there exists some S with at least s vertices and such that d(S) ≥ d?

Input

Input consists of several cases, each with the number of vertices n, the number of edges m, and m pairs x ⁠ ⁠ y (with x ≠ y), one for each edge of the graph, followed by s. The vertices are numbered from 0 to n − 1. Assume 1 ≤ n ≤ 10³, 0 ≤ m ≤ n(n − 1)/2, that there are no repeated edges, and 1 ≤ s ≤ n.

Output

For every case, print the required answer.