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^{3}, 0 ≤ *m* ≤ *n*(*n* − 1)/2,
that there are no repeated edges,
and 1 ≤ *s* ≤ *n*.

**Output**

For every case, print the required answer.

Public test cases

**Input**

6 6 0 1 1 2 2 0 0 3 1 4 2 5 3 6 6 0 1 1 2 2 0 0 3 1 4 2 5 4 2 1 1 0 2 2 0 2 3 2 0 1 0 2 2

**Output**

2 1 1 0 1

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Novè Concurs de Programació de la UPC - Final
- Date
- 2011-09-21