Задачі
Вершинне покриття
Вершинне покриття
Давайте навчимося розв'язувати наступну \textbf{NP}-задачу.
Вам дано граф і число \textbf{k}. Потрібно знайти у цьому графі таку множину з \textbf{k} вершин, що для кожного ребра даного графа хоча б один з двох його кінців лежить у вибраній множині вершин.
\InputFile
Перший рядок містить \textbf{3} числа --- \textbf{n}, \textbf{m} та \textbf{k}, де \textbf{n} --- кількість вершин у графі, \textbf{m} --- кількість ребер. Наступні \textbf{m} рядків містять опис ребер графу.
Відомо, що \textbf{1} ≤ \textbf{k} ≤ \textbf{n} ≤ \textbf{2000,} \textbf{1} ≤ \textbf{m} ≤ \textbf{10^5}. Степінь кожної вершини не менша \textbf{1}.
\OutputFile
Якщо шукана множина існує, у першому рядку виведіть слово \textbf{Yes}, а у другому \textbf{k} чисел --- номери вибраних вами вершин. Якщо ж множини не існує, виведіть слово \textbf{No}. Якщо можливих відповідей декілька, виведіть довільну. Одну вершину не можна брати у множину \textbf{2} рази, тобто усі \textbf{k} чисел повинні бути різними.
Вхідні дані #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