Tower of Hanoi Challenge

You are given a Tower of Hanoi puzzle with 3 rods labeled A, B, and C. In the initial configuration, all n disks (numbered from 1 to n with 1 being the smallest) are placed on rod A in increasing order (from top to bottom). You are also given a target configuration describing how the disks should be distributed among the 3 rods.

Your task is to determine whether the target configuration can be reached in at most m moves using the classical solution of the Tower of Hanoi problem.

Recall the minimal number of moves required to transfer n disks from one rod to another in the classical Tower of Hanoi puzzle is given by the formula: \(T(n)=2^n-1\).

Note:

• If the initial configuration is identical to the target configuration, the answer is "YES".
• The input consists of multiple test cases. Each test case starts with two numbers: n and m, followed by 3 lines describing the initial state and 3 lines describing the target state. The sequence of test cases is terminated by a line containing "0".

Output "YES" if the target configuration can be achieved within m moves, otherwise output "NO".

inputFormat

The input contains multiple test cases. For each test case, the first line contains an integer n (number of disks). If n is 0, it indicates the end of input. The second line contains an integer m (the maximum number of moves allowed). The next 3 lines describe the initial configuration of the three rods (each line begins with the rod label followed by zero or more disk numbers). The following 3 lines describe the target configuration in the same format.

All input is read from stdin.

outputFormat

For each test case, output a single line containing either "YES" or "NO", indicating whether the target configuration is achievable in no more than m moves.

The output is written to stdout.

## sample

3
3
A 1 2 3
B
C
A 3
B 2
C 1
3
7
A 1 2 3
B
C
A
B
C 1 2 3
3
5
A 1 2 3
B
C
A 1 2 3
B
C
0

NO
YES
YES

</p>