Chess Solitaire

문제

Chess Solitaire is a version of chess meant to be played by a single person. Okay, you probably figured that out on your own, but the exact rules are as follows: given a board with 2 or more chess pieces, none of which are pawns, find a series of captures which result in a single piece left on the board. Any piece that is moved must capture another piece, so if there are initially $mm$ pieces on the board, the solution involves $m-1m-1$ moves. An example puzzle and its solution is shown in Figure 1 (which corresponds to Sample Input 1):

Figure 1: Chess solitaire problem and a solution.

As a reminder, here are how the various chess pieces can capture other pieces:

For this problem, you will be given a chess solitaire puzzle and output a series to solve that puzzle.

입력

The input begins with a line $nn$ $mm$ where $nn$ ($2\le n\le 82\; \backslash leq\; n\; \backslash leq\; 8$) is the number of rows and columns in the board, and $mm$ ($2\le m\le 102\; \backslash leq\; m\; \backslash leq\; 10$) is the number of pieces in the problem. Following this are $mm$ lines of the form $pp$ $locloc$, where $pp$ is one of 'N', 'B', 'R', 'Q', 'K' indicating knight, bishop, rook, queen and king, respectively, and $locloc$ is a string of length 2 indicating the location of the piece on the board. The first character is an upper case letter indicating the row and the second character is an integer indicating the column (as shown in the figure above). All locations are valid and no two locations will be the same.

출력

Output $m-1m-1$ lines displaying the $m-1m-1$ moves to solve the problem. Each line will be of the form $pp$ $lo{c}_{1}loc\_1$ -> $lo{c}_{2}loc\_2$ indicating a move of piece $pp$ from location $lo{c}_{1}loc\_1$ to location $lo{c}_{2}loc\_2$. If there are multiple solutions, print the one which has a first move with the lexicographic lowest $lo{c}_{1}loc\_1$. If there is still a tie, print the one which has a first move with the lexicographic lowest $lo{c}_{2}loc\_2$. If there is still a tie, apply these rules to the second move, and so on.

If there is no possible solution to the puzzle, output No solution

5 5
N E3
Q C1
R C2
B C4
R A3

Q: C1 -> A3
R: C2 -> C4
N: E3 -> C4
N: C4 -> A3

4 4
Q D4
Q B1
Q C2
K A3

No solution