e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Вершинное покрытие

Вершинное покрытие

Давайте научимся решать следующую NP-задачу.

Вам дан граф и число k. Нужно найти в этом графе такое множество из k вершин, что для каждого ребра данного графа хотя бы один из двух концов ребра лежит в выбранном множестве вершин.

Входные данные

Первая строка содержит 3 числа n, m и k, где n — число вершин в графе, m — число ребер в графе. Следующие m строк содержат описание ребер графа.

Известно, что 1kn2000, 1m105. Степень каждой вершины не меньше 1.

Выходные данные

Если требуемое множество существует, на первой строке выведите слово Yes, а на второй k чисел — номера выбранных вами вершин. Если искомого множества не существует, то выведите слово No. Если возможных ответов несколько, выведите любой. Одну вершину нельзя брать в множество 2 раза, то есть все k чисел должны быть различны.

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
9 12 4
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
2 5
4 7
6 9
8 3
Выходные данные #1
Yes
2 4 6 8
Источник Зимняя школа, Харьков 2011, День 5