Qısqanc kraliça
Şahzadə və şahmat taxtasında N×N ölçüsündə qarşılaşdılar, burada bəzi hüceyrələr kəsilib. Hər biri digərini məğlub etmək istəyir. Tərəflərin optimal oyunu zamanı qələbə üçün lazım olan gedişlərin sayını müəyyənləşdirin (uduş mövqeyi, məğlub tərəfin başqa bir gediş edə bilmədiyi mövqedir - nümunələrə baxın).
Kəsilmiş hüceyrələrə daxil olmaq və ya onların üzərindən keçmək fiqurlara qadağandır. Eyni zamanda, kəsilmiş hüceyrələr üzərindən hücum etmək də mümkün deyil.
Əgər hansısa fiqur hərəkət edə bilmirsə, o təhlükəsiz sayılır və oyun heç-heçə ilə nəticələnir.
Məlumdur ki, şahzadə və şah fərqli hüceyrələrdə yerləşir və cari gedişdə hərəkət edən fiqur digərini məğlub edə bilməz.
Giriş verilənləri
Giriş faylının birinci sətirində iki ədəd N və M (2 ≤ N ≤ 12, 0 ≤ M ≤ 142) verilir, burada M - kəsilmiş hüceyrələrin sayıdır. Növbəti M sətirlər kəsilmiş hüceyrələrin koordinatlarını ehtiva edir və sonuncu sətirdə şahzadənin və şahın koordinatları, həmçinin kimin növbəsi olduğu haqqında məlumat verilir ('Q', əgər şahzadənin, 'K', əgər şahın).
Çıxış verilənləri
Üç mesajdan birini çıxarın:
"Queen wins in i moves", "King wins in i moves.", "The game will end in a draw". Burada i - müvafiq tərəfin qələbəsi üçün lazım olan ümumi gedişlərin sayıdır.