CF386D Game with Points

你正在玩如下游戏。在一个平面上有 $n$ 个点，这些点构成一个正 $n$ 边形的顶点。每个点用从 $1$ 到 $n$ 的整数编号，每对不同的点之间都有一条对角线，将对角线用 $26$ 种颜色中的一种着色。点用小写英文字母表示。有三颗棋子，分别放在三个不同的顶点上，所有棋子完全相同。每一步操作，你可以将一颗棋子沿某一条对角线移动到另一个空顶点，所走的对角线颜色必须与连接另外两枚棋子的对角线颜色相同。 你的目标是通过移动棋子，使得最终仅 $1$、$2$ 和 $3$ 号顶点被棋子占据，并且用最少的步数实现该目标。请编程实现该游戏的最优方案。

第一行一个整数 $n$，表示点的数量（$3 \leq n \leq 70$）。 第二行有三个用空格分隔的整数，表示棋子最初所在的三个顶点编号，编号范围为 $1$ 到 $n$。 接下来的 $n$ 行，每行有 $n$ 个符号，表示对角线的颜色的矩阵。颜色用小写英文字母表示。第 $i$ 行第 $j$ 列的符号表示点 $i$ 和点 $j$ 之间的对角线颜色。该矩阵是对称的，主对角线上是 `*`，表示点不能连接自身。

如果无法将棋子最终全部放到 $1$、$2$、$3$ 号顶点上，输出一行 $-1$。否则第一行输出所需的最小操作步数，接下来每行描述一个操作，每个操作用两个整数表示，分别为将棋子从哪个点移动到哪个点。如果存在多组最优方案，输出任意一组即可。

在第一个样例中，可以将 $4$ 号点上的棋子移动到 $1$ 号点，因为这两点间的对角线颜色为 'a'，且 $2$ 与 $3$ 号点之间的对角线颜色也是 'a'。经过这步操作后，棋子就处在 $1$、$2$ 和 $3$ 号点上了。 由 ChatGPT 5 翻译