Induced subgraphs

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.

Problem information

Author: Salvador Roura

Generation: 2026-01-25T10:01:20.593Z