The Tower of Hanoi consists of disks arranged in three piles numbered , , and . The disks all have distinct sizes, with disk being the smallest and disk being the largest. Larger disks cannot be placed on top of smaller disks. An arrangement of the disks can thus be represented uniquely by a sequence of digits, each being , , or , such that the digit represents the pile where disk is located.
A legal move consists of taking a single disk from the top of one pile, and placing it at the top of a different pile, such that the result is a valid arrangement. That is, a larger disk cannot be placed on top of a smaller disk. A move can be represented by two integers and , where the corresponding move takes the disk at the top of pile and places it at the top of pile .
Initially, all disks are in pile . You are given distinct arrangements, and must find a sequence of legal moves that visits all arrangements, in any order. It is permitted to visit an arrangement more than once. The sequence does not need to be optimal. However, it can have at most moves.
The arrangements are distinct.
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [50%]
Subtask 4 [10%]
No additional restrictions.
The first line contains two space-separated integers and .
The next lines each contain a string of digits, representing the arrangements to be visited.
The first line of output should contain an integer , the number of moves. Recall that may be at most .
The next lines should each contain two integers and , representing a legal move.
3 2 131 132
6 1 2 1 3 2 1 1 3 1 2 3 1