Game with Points

题意翻译

### 题目描述 有一个 $n(3\le n\le 70)$ 个结点的无向图，结点两两之间连边，每条边都有一个颜色，用一个小写字母表示，也就是说，最多只有 $26$ 种不同的颜色。初始有三个石头在三个不同的节点上。移动规则如下 1.选择一个石头 2.选中的石头只能沿着与另两个石头之间的边颜色相同的边走 3.不允许多个石头挤在同一个点上 问移动的最小步数以及在步数最小时的路径，如果选择任何一个点都无法让石头走到 $1,2,3$ ，输出 $-1$ 。 ### 输出格式 若选择某一个颜色可以让三个石头到达 $1,2,3$ ，第一行输出最小步数 $ans$ ，接下来输出 $ans$ 行，每行有两个整数 $u,v$ 表示一个石头从节点 $u$ 移动到了结点 $v$ 。 若无解则只输出一个 $-1$ 。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

4
2 3 4
*aba
a*ab
ba*b
abb*

输出样例 #1

1
4 1

输入样例 #2

4
2 3 4
*abc
a*ab
ba*b
cbb*

输出样例 #2

-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 $ .