Induced subgraphs P12120


Statement
 

pdf   zip

thehtml

Given an undirected graph G = (V, E), any SV 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 xy), one for each edge of the graph, followed by s. The vertices are numbered from 0 to n − 1. Assume 1 ≤ n ≤ 103, 0 ≤ mn(n − 1)/2, that there are no repeated edges, and 1 ≤ sn.

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