Minimum Moves for Tower of Hanoi

Given n distinct hollow discs numbered from \(1\) to \(n\) (in increasing order of size, where \(1\) is the smallest disc and \(n\) is the largest), these discs are initially stacked on three pegs labeled A, B, and C. The discs in each peg are arranged in a valid order (i.e. a larger disc is never placed on top of a smaller disc). This configuration is called the initial state.

Your task is to compute a sequence of moves with the minimum number of steps to transform the initial state into the target state. The target state is defined as having all discs successfully moved onto peg C in proper order (i.e. from bottom to top: \(n, n-1, \ldots, 1\)).

During each move, you are only allowed to move one disc at a time and you can never place a larger disc on top of a smaller disc.

Note: The input is guaranteed to be a valid configuration. For the purpose of this problem, the test cases will use the classical Tower of Hanoi initial state where all discs are initially on peg A in descending order (largest at the bottom) and pegs B and C are empty.

inputFormat

The input consists of 4 lines:

• The first line contains an integer \(n\) (the number of discs).
• The second line describes peg A: the first integer \(k_A\) is the number of discs on peg A, followed by \(k_A\) integers representing the discs from bottom to top.
• The third line describes peg B in the same format.
• The fourth line describes peg C in the same format.

The target state is defined as peg A and peg B being empty and peg C containing all \(n\) discs in descending order (from bottom to top: \(n, n-1, \ldots, 1\)).

outputFormat

The output starts with an integer representing the minimum number of moves required. Then output each move on a new line in the format "X Y" (without quotes), indicating that the top disc from peg X is moved to peg Y.

sample

1
1 1
0
0

1
A C