您正在玩以下游戏。平面上有n个点。它们是正 n 多边形的顶点。点用 1 到 n 的整数标记。每对不同的点都由一条对角线连接,该对角线采用 26 种颜色之一着色。点用小写英文字母表示。三块石头位于三个不同的顶点。所有的石头都是一样的。通过一次移动,您可以将石头沿某条对角线移动到另一个自由顶点。这条对角线的颜色必须与连接另外两块石头的对角线的颜色相同。
你的目标是以这样的方式移动石子,使得石子占据的唯一顶点是 1、2 和 3。你必须使用最少的移动次数达到这样的位置。编写一个以最佳方式玩这个游戏的程序。
输入
第一行有一个整数 n (3 ≤ n ≤ 70) — 点数。第二行有三个空格分隔的整数,从 1 到 n - 顶点数,石头最初所在的位置。
以下 n 行中的每一行包含 n 个符号 - 表示对角线颜色的矩阵。颜色用小写英文字母表示。第i行的符号j表示点i和j之间的对角线的颜色。矩阵是对称的,因此第 i 行的第 j 个符号等于第 j 行的第 i 个符号。主对角线充满“*”符号,因为没有对角线,将点连接到其自身。
输出
如果无法在顶点 1、2 和 3 上放置棋子,则在一行上打印 -1。否则,在第一行打印所需的最小移动次数,并在接下来的行中打印每个移动的描述,每行一个移动。要描述一次移动,请打印两个整数。移走石头的起点和移动石头的终点。如果有多个最优解,则打印其中任意一个。
示例
输入 #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
注意
在第一个示例中,我们可以将棋子从点 4 移动到点 1,因为这些点由颜色“a”的对角线连接,而对角线连接点 2 和 3(其他棋子所在的位置)由相同颜色的对角线连接。之后,棋子将位于点 1、2 和 3 上。