Zirvə örtüyü#1873
Gəlin, aşağıdakı NP-problemi həll etməyi öyrənək.
Sizə bir qraf və ədədi verilir. Elə ədəd zirvədən ibarət bir çoxluq tapmalısınız ki, verilmiş qrafdakı hər bir kənar üçün onun ən azı bir ucu seçilmiş zirvələrin içində olsun.
Birinci sətirdə ədəd tam ədəd verilir: , və , burada qrafın zirvələrinin, kənarlarının, isə seçməli olduğunuz zirvələrin sayını göstərir. Sonrakı sətirdə qrafın kənarları təsvir olunur.
Zəmanət verilir ki, 1 \leq k \leq n \leq 2000, 1 \leq m \leq 10^5. Hər bir zirvənin dərəcəsi ən azı -dir.
Əgər belə bir çoxluq mövcuddursa, ilk sətirdə Yes çap edin, ikinci sətirdə isə seçilmiş zirvələrin indekslərini göstərən fərqli tam ədəd yazın. Əgər belə çoxluq mövcud deyilsə, No yazın. Bir neçə mümkün cavab olduqda, istənilən birini verə bilərsiniz. Heç bir zirvəni iki dəfə daxil edə bilməzsiniz, yəni seçilmiş hər ədəd fərqli olmalıdır.
Nümunə 1