Krallığın zəbt edilməsi
Sehrli bir krallıqda, hər biri bir-biri ilə yollarla bağlı olan N şəhər mövcuddur. Bu yollar qədim zamanlarda İşıq və Qaranlıq qüvvələri tərəfindən inşa edilmişdir. İşıq qüvvələrinin yolları ağ daşla, Qaranlıq qüvvələrinin yolları isə qara daşla döşənmişdir. Sehrli cazibələr bu yolları qoruduğundan, yaxşı məxluqlar qara daşlı yollardan, pis məxluqlar isə ağ daşlı yollardan keçə bilməz.
Bir zamanlar insanlar öz hökmdarlarını seçməyə qərar verdilər və ali sehrbazları krallıqdan uzaqlaşdırdılar. Lakin son zamanlarda İşıq və Qaranlıq qüvvələrinin ali sehrbazları bir razılığa gəlib, krallığı ələ keçirmək qərarına gəldilər. Bunun üçün onlar bəzi şəhərlərə sehrbazlar göndərmək istəyirlər ki, həmin şəhərləri və qonşu şəhərləri nəzarət altına alsınlar.
Daha dəqiq desək, əgər işıq sehrbazı bir şəhərə göndərilərsə, o, həmin şəhəri və birbaşa ağ yollarla bağlı olan bütün şəhərləri nəzarət altına alacaq. Eyni şəkildə, qara sehrbaz göndərildiyi şəhərdən başqa, birbaşa qara yollarla bağlı olan bütün şəhərləri də nəzarət altına alacaq. Krallığı ələ keçirmək üçün bütün şəhərləri nəzarət altına almaq lazımdır.
Lakin ələ keçirmə planı hazırlanarkən iki problem ortaya çıxdı. Birincisi, sehrbaz yalnız o zaman əməliyyatda iştirak etməyə razıdır ki, krallığa göndərilən bütün sehrbazlar onun təmsil etdiyi qüvvəyə aid olsunlar. Yəni ya bütün sehrbazlar işıq olmalıdır, ya da hamısı qara olmalıdır. İkincisi, krallığa göndərilə biləcək sehrbazların ümumi sayı K-dan çox olmamalıdır.
Ali sehrbazların yeganə ümidi K-nın kifayət qədər böyük olmasıdır, yəni 2^K ≥ N.
Müəyyən edin, krallığı ələ keçirmək üçün işıq, yoxsa qara sehrbazlardan istifadə etmək lazımdır və onları hansı şəhərlərə göndərmək lazımdır.
Giriş verilənləri
Giriş faylının birinci sətiri tam ədədlər N və K (2 ≤ N ≤ 256, 2^K ≥ N, K ≤ N) ehtiva edir.
Növbəti N sətir hər biri N tam ədəd ehtiva edir. Bu sətirlərin i-ci mövqeyində 0 rəqəmi yerləşir ki, bu da şəhərin öz-özü ilə yol ilə birləşmədiyini göstərir. Bütün j <> i üçün bu sətirlərin j-ci mövqeyindəki rəqəm 1-ə bərabərdir, əgər i-ci şəhər j-ci ilə ağ yolla birləşirsə və 2-yə bərabərdir, əgər onlar qara yolla birləşirsə. Sətirlərdəki rəqəmlər boşluqla ayrılmışdır.
Giriş məlumatlarının düzgün olduğu təmin edilir, yəni əgər i-ci şəhər j-ci ilə ağ yolla birləşirsə, onda j-ci də i-ci ilə ağ yolla birləşir, qara yollar üçün də eyni qayda keçərlidir.
Çıxış verilənləri
Əgər verilmiş şərtlərlə krallığı ələ keçirmək mümkün deyilsə, çıxış faylına tək 0 rəqəmi yazın.
Əks halda, birinci sətirdə krallığı işıq sehrbazları ilə ələ keçirmək mümkün olarsa 1, qara sehrbazlardan istifadə etmək lazım gələrsə 2 yazın. Növbəti sətirdə istifadə olunan sehrbazların sayı L ≤ K yazın. Üçüncü sətir L tam ədəd ehtiva etməlidir - sehrbazların göndəriləcəyi şəhərlərin nömrələri.
Qeyd edək ki, sizə L-ı minimallaşdırmaq lazım deyil. Əgər bir neçə həll yolu varsa, istənilənini çıxarın.