Zirvə örtüyü
Gəlin, növbəti NP-məsələsini həll etməyi öyrənək.
Sizə bir qraf və k ədədi verilir. Bu qrafda elə bir k ədədindən ibarət çoxluq tapmaq lazımdır ki, verilmiş qrafın hər bir qırağı üçün onun iki ucundan ən azı biri seçilmiş çoxluqda olsun.
Giriş verilənləri
Birinci sətir 3 ədəd — n, m və k ədədlərini ehtiva edir, burada n — qrafdakı zirvələrin sayı, m — qıraqların sayı. Növbəti m sətir qrafın qıraqlarının təsvirini ehtiva edir.
Məlumdur ki, 1 ≤ k ≤ n ≤ 2000, 1 ≤ m ≤ 10^5. Hər bir zirvənin dərəcəsi 1-dən kiçik deyil.
Çıxış verilənləri
Əgər axtarılan çoxluq varsa, birinci sətirdə Yes sözünü, ikinci sətirdə isə seçdiyiniz zirvələrin k ədədini çıxarın. Əgər çoxluq yoxdursa, No sözünü çıxarın. Əgər bir neçə mümkün cavab varsa, istənilən birini çıxarın. Bir zirvəni 2 dəfə çoxluğa daxil etmək olmaz, yəni bütün k ədədləri fərqli olmalıdır.