Вершинное покрытие
Давайте научимся решать следующую NP-задачу.
Вам дан граф и число k. Нужно найти в этом графе такое множество из k вершин, что для каждого ребра данного графа хотя бы один из двух концов ребра лежит в выбранном множестве вершин.
Входные данные
Первая строка содержит 3 числа n, m и k, где n — число вершин в графе, m — число ребер в графе. Следующие m строк содержат описание ребер графа.
Известно, что 1 ≤ k ≤ n ≤ 2000, 1 ≤ m ≤ 10^5. Степень каждой вершины не меньше 1.
Выходные данные
Если требуемое множество существует, на первой строке выведите слово Yes, а на второй k чисел — номера выбранных вами вершин. Если искомого множества не существует, то выведите слово No. Если возможных ответов несколько, выведите любой. Одну вершину нельзя брать в множество 2 раза, то есть все k чисел должны быть различны.