Ревнива королева#2487
Королева та Король знаходяться на шахівниці розміром N \times N, де деякі клітини вирізані. Кожна фігура хоче захопити іншу. Визначте мінімальну кількість ходів, необхідних для перемоги однієї зі сторін, якщо обидві грають оптимально. Виграшною є така позиція, у якій сторона, що програє, не може уникнути ходу під удар (див. приклади).
Заборонено ставати, перестрибувати чи бити через вирізані клітини.
Якщо фігура опиняється у пастці, вона вважається у безпеці, і гра завершується у нічию.
Гарантується, що Королева та Король починають на різних клітинах, і гравець, чия черга ходити, не може одразу захопити іншого.
Перший рядок містить два цілі числа та (2 \leq N \leq 12, 0 \leq M \leq 142), де — кількість вирізаних клітин. Наступні рядків описують координати вирізаних клітин. Останній рядок містить координати Королеви та Короля, а також, чия черга ходити (Q — хід Королеви, K — хід Короля).
Виведіть одне з наступних повідомлень:
Queen wins in moves.,
King wins in moves.,
або The game will end in a draw.
Тут — загальна кількість ходів, необхідних для перемоги відповідної сторони.
Приклад 1