Problem G

The Adventure in Panda Land Part 2: Panda Tower

Problem Description

There are three altars in Panda Land. On the first altar, there is a stone tower built by arranging N stones of various sizes on top of each other. The arrangement was made such that there’s no larger stone put on top of a smaller one.

Li Ming, the panda chief, has decided to move the stone tower to the P-th altar. However, he can only move a single stone (one on the top) at a time from one altar to another. No stone is allowed to be put on any other places except on the altars. There is at most one stack of stones on any altars and no larger stone should be put on top of smaller stone.

Days passed, and Li Ming hasn’t completed the job, because he just moved stones in a random order, although he’s still following to the given rules. Frustrated by this problem, he decided to come to the human world and asked for help (yeah, you understand what he wants).

Given the current condition for each altar, help Li Ming to find the moves sequence needed to completely move all stones to the P-th altar. The number of moves should not exceed 2^N-1, otherwise Li Ming will get more frustrated than ever (and if it happens, run for your life).

Input Speficication

The first line of input contains an integer T, the number of test cases follow.

Each test case begins with N (4 <= N <= 15), the number of stones. Each of the three altar’s condition will be described in two lines. The first line contains Si, the number of stone on ith altar. The second line contains Si integers denoting each stone’s size on ith altar in descending order. The sum of all stones in three altars will be equal to N. The last line of each case contains P (1 <= P <= 3), the target altar.

Output Speficication

For each case, print the L (0 <= L <= 2^N-1), the number of moves needed to completely moves all stones to the Pth altar. The next L line should describe the moves sequence. Each line contains two integer A and B (1 <= A, B <= 3), which means “move the top stone on Ath altar into the top of Bth altar”. If there is more than one such sequence, just output any of them.

If there is no such sequence below 2^N-1, print “impossible” (without quotes) in a single line, no need to print L and the sequence.

2
4
4
4 3 2 1
0

0

3
5
1
5
2
4 2
2
3 1
2

15
1 2
1 3
2 3
1 2
3 1
3 2
1 2
1 3
2 3
2 1
3 1
2 3
1 2
1 3
2 3
29
3 2
3 1
2 3
2 1
3 1
2 3
1 3
1 2
3 2
1 3
2 1
2 3
1 3
1 2
3 1
3 2
1 2
3 1
2 3
2 1
3 1
3 2
1 2
1 3
2 3
1 2
3 1
3 2
1 2