题目描述

国际象棋接龙是一种供单人游玩的国际象棋变体。你大概已经从名字猜到了这一点，但它的确切规则如下：给定一个棋盘，棋盘上有至少两个棋子且没有兵，找出一系列吃子操作，使棋盘上最终只剩一个棋子。

每次移动的棋子都必须吃掉另一个棋子。因此，如果棋盘最初有 $m$ 个棋子，解法就恰好包含 $m-1$ 步。图 1 展示了一个谜题及其解法，对应样例一。

各类棋子的吃子走法与普通国际象棋相同，图 2 和图 3 给出了提示。

本题给定一个国际象棋接龙谜题，请输出一系列操作将其解出。

:::align{center}

:::

输入格式

第一行包含两个整数 $n,m$，其中 $2\le n\le 8$ 表示棋盘的行数和列数，$2\le m\le 10$ 表示棋子数量。

接下来的 $m$ 行均为 $p$ loc 的形式。$p$ 为 N、B、R、Q 或 K，依次表示马、象、车、后和王；loc 是长度为 $2$ 的字符串，表示棋子位置。第一个字符为大写字母，表示行；第二个字符为数字，表示列，如图所示。所有位置都合法，且任意两个棋子的位置不同。

输出格式

输出 $m-1$ 行，表示解题所需的 $m-1$ 步操作。每行为 $p$: loc1 -> loc2 的形式，表示棋子 $p$ 从位置 loc1 移动到位置 loc2 并吃掉该处棋子。

如果有多个解，先选择第一步起点 loc1 字典序最小的解；仍有并列时，选择第一步终点 loc2 字典序最小的解；如果仍然并列，就对第二步应用同样规则，依此类推。

如果谜题无解，输出 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