CF386D.Game with Points

You are playing the following game. There are n points on a plane. They are the vertices of a regular n-polygon. Points are labeled with integer numbers from 1 to n. Each pair of distinct points is connected by a diagonal, which is colored in one of 26 colors. Points are denoted by lowercase English letters. There are three stones positioned on three distinct vertices. All stones are the same. With one move you can move the stone to another free vertex along some diagonal. The color of this diagonal must be the same as the color of the diagonal, connecting another two stones.

Your goal is to move stones in such way that the only vertices occupied by stones are 1, 2 and 3. You must achieve such position using minimal number of moves. Write a program which plays this game in an optimal way.

你正在玩以下游戏：平面上有 $n$ 个点，它们构成一个正 $n$ 边形的顶点。这些点按整数 $1$ 到 $n$ 编号。每对不同的点之间都连有一条对角线，且每条对角线被染成 $26$ 种颜色之一。点用小写英文字母表示。初始时，有三颗相同的石子分别位于三个互不相同的顶点上。每次操作中，你可以沿某条对角线将一颗石子移动到另一个空闲的顶点；该对角线的颜色必须与连接其余两颗石子的那条对角线的颜色相同。

你的目标是通过若干次操作，使得最终仅有编号为 $1$、$2$ 和 $3$ 的三个顶点被石子占据。你需要以最少的操作次数达成这一目标。请编写一个程序，以最优方式完成该游戏。

In the first line there is one integer n (3 ≤ n ≤ 70) — the number of points. In the second line there are three space-separated integer from 1 to n — numbers of vertices, where stones are initially located.

Each of the following n lines contains n symbols — the matrix denoting the colors of the diagonals. Colors are denoted by lowercase English letters. The symbol j of line i denotes the color of diagonal between points i and j. Matrix is symmetric, so j-th symbol of i-th line is equal to i-th symbol of j-th line. Main diagonal is filled with '*' symbols because there is no diagonal, connecting point to itself.

第一行包含一个整数 $n$（$3 \leq n \leq 70$）—— 点的数量。
第二行包含三个用空格分隔的、取值范围为 $1$ 到 $n$ 的整数——初始时放置石子的三个顶点的编号。

接下来的 $n$ 行，每行包含 $n$ 个字符，构成一个表示对角线颜色的矩阵。颜色用小写英文字母表示。第 $i$ 行的第 $j$ 个字符表示连接第 $i$ 个点与第 $j$ 个点的对角线的颜色。该矩阵是对称的，因此第 $i$ 行第 $j$ 个字符等于第 $j$ 行第 $i$ 个字符。主对角线上的字符均为 '*'，因为不存在连接一个点与其自身的对角线。

If there is no way to put stones on vertices 1, 2 and 3, print -1 on a single line. Otherwise, on the first line print minimal required number of moves and in the next lines print the description of each move, one move per line. To describe a move print two integers. The point from which to remove the stone, and the point to which move the stone. If there are several optimal solutions, print any of them.

如果无法在顶点 1、2 和 3 上放置石子，则在单独一行输出 -1。否则，第一行输出所需的最少移动次数，接下来的每一行描述一次移动（每次移动占一行）。每次移动用两个整数表示：移出石子的顶点编号，以及移入石子的顶点编号。若存在多个最优解，输出任意一个即可。

In the first example we can move stone from point 4 to point 1 because this points are connected by the diagonal of color 'a' and the diagonal connection point 2 and 3, where the other stones are located, are connected by the diagonal of the same color. After that stones will be on the points 1, 2 and 3.

在第一个示例中，我们可以将位于点 4 的石子移动到点 1，因为这两点由颜色为 'a' 的对角线相连，且该对角线还连接了点 2 和点 3（即其余石子所在的位置），而点 2 和点 3 之间也由同色（'a'）的对角线相连。移动之后，石子将位于点 1、2 和 3 上。