A museum has K2 triangular rooms, where ( ). All rooms have the same size and there is exactly one guard in each room. The shape of the museum itself is also triangular, as exemplified in Figure 1, where a museum with 32 triangular rooms is shown. The names AA, BB, CC, ... are guard names (a guard name is a sequence of at most 10 letters). Thus guard DD is at the top room of the initial configuration presented in Figure 1.
Each two adjacent rooms are separated by exactly one wall, which has a door that connects the rooms. Since the guards would also like to appreciate the art in the museum, they agree to exchange their positions, thus forming a new configuration, previously agreed upon. The order in which the guards move to their new positions obey a few rules. These rules, for security reasons, do not allow guards to leave their positions all at the same time. The only way they can move is by exchanging their positions with guards in adjacent rooms, one pair at a time.
The objective of this problem is to find a sequence of exchanges between guards that leads to the new configuration.
Initial Configuration New Configuration /\ /\ /DD\ /AA\ /____\ /____\ /\ /\ /\ /\ /FF\AA/CC\ ===> /BB\CC/DD\ /____\/____\ /____\/____\ /\ /\ /\ /\ /\ /\ /BB\EE/II\GG/HH\ /EE\FF/GG\HH/II\ /____\/____\/____\ /____\/____\/____\ Figure 1.
There is at least one blank space between these strings of letters. The last line of the input file contains only the value 0 (zero) which should not be processed.
Instances are NOT separated by blank lines.
3 DD FF AA CC BB EE II GG HH AA BB CC DD EE FF GG HH II 2 D A B C A B C D 0
6 GG II HH II EE BB DD AA BB FF DD CC 3 A B A D C D