Представьте, что Вы играете в следующую игру. Имеется n точек, являющихся вершинами правильного n-угольника. Точки пронумерованы целыми числами от 1 до n. Каждая пара точек соединена отрезком некоторого цвета. Различных цветов не более 26, они обозначаются строчными латинскими буквами. В трех различных точках стоит по фишке. Все фишки одинаковые. За один ход Вы можете взять любую из фишек и передвинуть ее в другую точку. При этом цвет отрезка, по которому Вы можете передвинуть фишку, должен совпадать с цветом отрезка, соединяющего точки, в которых находятся две другие фишки. Нельзя перемещать фишку в точку, в которой уже находится другая фишка. Ваша задача состоит в том, чтобы за наименьшее количество ходов добиться того, чтобы фишки находились в точках с номерами 1, 2 и 3. Напишите программу, которая оптимальным образом играет в эту игру.
Выходные данные
Если не существует ни одной последовательности ходов, после которых фишки оказываются в точках с номерами 1, 2 и 3, выведите в единственной строке число -1. Если же решение существует, то в первой строке выведите наименьшее возможное количество ходов, а далее сами ходы. Для описания очередного хода в отдельной строке выведите два целых числа через пробел — номер точки, откуда следует взять фишку, и номер точки, куда ее следует передвинуть. Если оптимальных последовательностей ходов несколько, выведите любую из них.
Примечание
В первом примере мы можем передвинуть фишку из точки 4 в точку 1, потому что они соединены отрезком цвета 'a', как и точки 2 и 3, в которых находятся две другие фишки. После этого хода фишки находятся в точках 1, 2 и 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3 4
*aba
a*ab
ba*b
abb*
|
1
4 1
|
|
2
|
4
2 3 4
*abc
a*ab
ba*b
cbb*
|
-1
|