e-olymp
Competitions

Summer School 2011 in Sevastopol, Day 7

Ревнивая королева

Королева и король встретились на шахматной доске N×N, на которой вырезаны некоторые клетки. Каждый из них хочет съесть другого. Выведите количество ходов, необходимое для этого, при оптимальной игре сторон (выигрышной позицией считается та, в которой проигрывающей стороне некуда деться, кроме как встать под бой - см. примеры).

Ходить на вырезанные клетки или перепрыгивать через них фигурам запрещается. Бить через вырезанные клетки, естественно, тоже нельзя.

Если какая-то из фигур заперта, то она считается находящейся в безопасности, и игра закончится вничью.

Известно, что ферзь и король находятся на разных клетках, и на текущем ходу фигура, которая ходит, не может съесть другую.

Входные данные

В первой строке входного файла даны два числа N и M (2N12, 0M142), где M - число вырезанных клеток. Следующие M строк содержат координаты вырезанных клеток, а в последней строке даны координаты королевы и координаты короля, а также информация о том, чей сейчас ход ('Q', если королевы, 'K', если короля).

Выходные данные

Выведите одно из трёх сообщений:

"Queen wins in i moves", "King wins in i moves.", "The game will end in a draw". Здесь i - суммарное число ходов, необходимых для выигрыша соответствующей стороне.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 0
3 2 1 3 K
Output example #1
Queen wins in 0 moves