## New Year's '18 P5 - Hanoi Heuristics

View as PDF

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types

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.

#### Constraints

The arrangements are distinct.

#### Input Specification

The first line contains two space-separated integers and .

The next lines each contain a string of digits, representing the arrangements to be visited.

#### Output Specification

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.

#### Sample Input

3 2
131
132

#### Sample Output

6
1 2
1 3
2 1
1 3
1 2
3 1