P17346 [ECNA 2025] Chess Solitaire

国际象棋接龙是一种供单人游玩的国际象棋变体。你大概已经从名字猜到了这一点，但它的确切规则如下：给定一个棋盘，棋盘上有至少两个棋子且没有兵，找出一系列吃子操作，使棋盘上最终只剩一个棋子。 每次移动的棋子都必须吃掉另一个棋子。因此，如果棋盘最初有 $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`。