Vertex Cover
Let's explore how to solve the following NP-problem.
You are given a graph and a number k. Your task is to find a set of k vertices such that for every edge in the graph, at least one of its endpoints is included in this set of vertices.
Input
The first line contains 3 integers: n, m, and k. Here, n represents the number of vertices in the graph, m is the number of edges, and k is the number of vertices you need to select. The following m lines describe the edges of the graph.
It is guaranteed that 1 ≤ k ≤ n ≤ 2000, and 1 ≤ m ≤ 10^5. Each vertex has a degree of at least 1.
Output
If such a set exists, print Yes on the first line. On the second line, print k distinct integers, representing the indices of the selected vertices. If no such set exists, print No. If there are multiple valid solutions, you may output any one of them. Note that a vertex cannot be selected more than once, so all k numbers must be unique.