Jealous Queen
The Queen and the King are positioned on an N×N chessboard, where certain squares are unavailable for play. Each player aims to capture the other. Your task is to determine the number of moves needed for one to capture the other, assuming both play optimally. A winning position is defined as one where the opponent has no option but to move into a position where they can be captured (refer to examples for clarity).
Pieces cannot move onto or jump over unavailable squares, nor can they capture over them.
If a piece becomes trapped, it is considered safe, resulting in a draw.
It is guaranteed that the queen and the king start on different squares, and on the current move, the piece that moves cannot immediately capture the other.
Input
The first line of the input contains two integers N and M (2 ≤ N ≤ 12, 0 ≤ M ≤ 142), where M is the number of unavailable squares. The following M lines list the coordinates of these unavailable squares. The final line provides the coordinates of the queen and the king, along with whose turn it is ('Q' for the queen's turn, 'K' for the king's turn).
Output
Print one of the following messages:
"Queen wins in i moves", "King wins in i moves.", or "The game will end in a draw". Here, i represents the number of moves required for the respective side to secure a win.