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++