Krallığın zəbt edilməsi#3056
Sehrli bir krallıqda şəhər var və hər bir şəhər cütü arasında yol var. Bu yollar çoxdan işıq və qaranlıq qüvvələri tərəfindən çəkilmişdir: İşıq qüvvələrinin çəkdiyi yollar ağ daşlarla, Qaranlıq qüvvələrinin çəkdiyi yollar isə qara daşlarla döşənmişdir. Sehrli cazibələrə görə, yaxşı varlıqlar qara daşla döşənmiş yollardan gedə bilmir, pis varlıqlar isə ağ yolda hərəkət edə bilmir.
Çoxdan bəri insanlar öz hökmdarlarını seçməyə qərar verdilər və ali sehrbazları krallıqdan qovdular. Lakin yaxınlarda işıq və qaranlıq qüvvələrinin ali sehrbazları krallığı qaytarmaq üçün razılaşma əldə etdilər. Bu məqsədə çatmaq üçün onlar bəzi şəhərlərə sehrbaz göndərməyi planlaşdırırlar ki, həmin şəhərlər və onlara qonşu olan şəhərlər onların nəzarətinə keçsin.
Dəqiq desək, əgər bir şəhərə İşıq sehrbazı göndərilirsə, o sehrbaz həmin şəhəri və həmin şəhərə birbaşa ağ yol ilə birləşən bütün şəhərləri nəzarətə alacaq. Eyni qayda ilə, Qaranlıq sehrbazı, göndərildiyi şəhərlə yanaşı, o şəhərə birbaşa qara yol ilə birləşən bütün şəhərləri də nəzarətə alacaq. Krallığı ələ keçirmək üçün, bütün şəhərlərin nəzarətə alınması vacibdir.
Lakin planda iki çətinlik ortaya çıxıb. Birinci çətinlik ondan ibarətdir ki, sehrbaz yalnız o halda iştirak edəcək ki, krallığa göndərilən bütün sehrbazlar, onun təmsil etdiyi qüvvəyə aid olsun. Yəni, ya bütün sehrbazlar işıq qüvvələrinin, ya da hamısı qaranlıq qüvvələrinin olmalıdır. İkincisi isə, krallığa göndərilən sehrbazların ümumi sayı -dan çox olmamalıdır.
Ali sehrbazlar ümid edirlər ki, kifayət qədər böyukdür, yəni 2^K \geq N.
Tapın, krallığı ələ keçirmək üçün yalnız İşıq sehrbazlarından, yoxsa yalnız Qaranlıq sehrbazlarından istifadə etmək lazımdır və sehrbazlar hansı şəhərlərə göndərilməlidir.
Giriş faylının birinci sətrində və ədədləri verilir (2 \leq N \leq 256, 2^K \geq N, K \leq N).
Sonrakı sətrin hər birində ədəd var. -ci sətrin -ci yerində dayanır, bu o deməkdir ki, şəhər özü ilə yol vasitəsilə birləşmir. j \neq i olduqda isə, -ci şəhər -ci şəhərlə ağ yol ilə birləşirsə, -ci yerdə yazılır, əgər qara yol ilə birləşirsə, yazılır. Ədədlər boşluqla ayrılmışdır.
Zəmanət verilir ki, giriş məlumatları doğrudur: əgər -ci şəhər -ci şəhərlə ağ yol ilə birləşirsə, -ci şəhər də -ci ilə ağ yol ilə birləşir, qara yol üçün də eynidir.
Əgər verilmiş şərtlərlə krallığı ələ keçirmək mümkün deyilsə, bir ədəd çıxış verin.
Əks halda, birinci sətirdə əgər krallığı İşıq sehrbazları ilə ələ keçirmək mümkündürsə, , yalnız Qaranlıq sehrbazları ilə mümkündürsə çıxış verin. Növbəti sətirdə istifadə olunan sehrbazların sayı L \leq K yazılmalıdır. Üçüncü sətirdə isə, sehrbazların göndəriləcəyi şəhərlərin nömrələri verilməlidir.
Qeyd: ədədi minimallaşdırmaq tələb olunmur. Bir neçə həll varsa, istənilənini çıxış verə bilərsiniz.
Nümunə 1