Jealous Queen#2487
The Queen and the King are on an N \times N chessboard, where some squares are cut out. Each piece wants to capture the other. Determine the minimum number of moves required for one side to win, assuming both play optimally. A winning position is one in which the losing side cannot avoid moving into capture (see examples).
It is forbidden to move onto, jump over, or capture across cut out squares.
If a piece becomes trapped, it is considered safe, and the game ends in a draw.
It is guaranteed that the Queen and the King start on different squares, and the piece whose turn it is cannot immediately capture the other.
The first line contains two integers and (2 \leq N \leq 12, 0 \leq M \leq 142), where is the number of cut out squares. The next lines describe the coordinates of the cut out squares. The last line contains the coordinates of the Queen and the King, and whose turn it is (Q for Queen, K for King).
Output one of the following messages:
Queen wins in moves.,
King wins in moves.,
or The game will end in a draw.
Here, is the total number of moves required for the respective side to win.
Example 1