Description

There are $n$ hollow circular disks of distinct sizes, labeled from $1$ to $n$ in ascending order by size. These $n$ disks are arbitrarily nested on three pegs labeled $A$, $B$, $C$. This configuration is called the initial state.

Your task is to find a shortest sequence of moves that transforms the initial state into the target state.

The move rules are as follows:

• Only one disk may be moved at a time.
• A larger disk may not be placed on top of a smaller disk.

Input Format

The first line contains an integer $n$, the total number of disks present in the states.

The next three lines each contain several integers, describing the disks on pegs $A$, $B$, $C$ in the initial state, listed from bottom to top. If a line contains only the single number $0$, that peg has no disk.

The following three lines each contain several integers, describing the disks on pegs $A$, $B$, $C$ in the target state, listed from bottom to top. If a line contains only the single number $0$, that peg has no disk.

Output Format

Several lines, each containing a string in the format move I from P to Q, representing a single move.

Then output one line with one integer, the minimum number of moves from the initial state to the target state.

5
3 3 2 1
2 5 4
0
1 2
3 5 4 3
1 1

move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to B
move 2 from C to A
move 1 from B to C
7

Hint

Constraints: For $100\%$ of the testdata, $1 \le n \le 45$, and $1 \le$ each disk's index $\le n$.

Each line’s disk description is listed from bottom to top.

Translated by ChatGPT 5