Induced subgraphs P12120

Given an undirected graph $G = (V, E)$, any $S \subseteq 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) \ge d$?

Input

Input consists of several cases, each with the number of vertices $n$, the number of edges $m$, and $m$ pairs $x \enspace y$ (with $x \ne y$), one for each edge of the graph, followed by $s$. The vertices are numbered from 0 to $n - 1$. Assume $1 \le n \le 10^3$, $0 \le m \le n(n - 1)/2$, that there are no repeated edges, and $1 \le s \le n$.

Output

For every case, print the required answer.