D. Игра с точками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте, что Вы играете в следующую игру. Имеется n точек, являющихся вершинами правильного n-угольника. Точки пронумерованы целыми числами от 1 до n. Каждая пара точек соединена отрезком некоторого цвета. Различных цветов не более 26, они обозначаются строчными латинскими буквами. В трех различных точках стоит по фишке. Все фишки одинаковые. За один ход Вы можете взять любую из фишек и передвинуть ее в другую точку. При этом цвет отрезка, по которому Вы можете передвинуть фишку, должен совпадать с цветом отрезка, соединяющего точки, в которых находятся две другие фишки. Нельзя перемещать фишку в точку, в которой уже находится другая фишка. Ваша задача состоит в том, чтобы за наименьшее количество ходов добиться того, чтобы фишки находились в точках с номерами 1, 2 и 3. Напишите программу, которая оптимальным образом играет в эту игру.

Входные данные

В первой строке записано целое число n (3 ≤ n ≤ 70) — количество точек. Во второй строке записаны три различных целых числа от 1 до n — номера точек, в которых изначально находятся фишки. Каждая из следующих строк содержит по n символов — это матрица, задающая цвета отрезков. Цвета задаются строчными буквами латинского алфавита. Символ с номером j в i-й строке матрицы обозначает цвет отрезка между точками i и j. Матрица симметрична, то есть j-й символ i-й строки совпадает с i-м символом j-й строки. На главной диагонали матрицы стоят символы '*', потому что не существует отрезка, соединяющего точку саму с собой.

Выходные данные

Если не существует ни одной последовательности ходов, после которых фишки оказываются в точках с номерами 1, 2 и 3, выведите в единственной строке число -1. Если же решение существует, то в первой строке выведите наименьшее возможное количество ходов, а далее сами ходы. Для описания очередного хода в отдельной строке выведите два целых числа через пробел — номер точки, откуда следует взять фишку, и номер точки, куда ее следует передвинуть. Если оптимальных последовательностей ходов несколько, выведите любую из них.

Примеры
Входные данные
4
2 3 4
*aba
a*ab
ba*b
abb*
Выходные данные
1
4 1
Входные данные
4
2 3 4
*abc
a*ab
ba*b
cbb*
Выходные данные
-1
Примечание

В первом примере мы можем передвинуть фишку из точки 4 в точку 1, потому что они соединены отрезком цвета 'a', как и точки 2 и 3, в которых находятся две другие фишки. После этого хода фишки находятся в точках 1, 2 и 3.