A Game of Cards
Alice and Bob got bored and came up with a new game.
They put N cards in a row on a table. The cards have IDs 1 to N from left to right. Each card has a positive integer written on it.
You can perform the following operation on the cards:
Choose any two adjacent cards. If the cards have different numbers written on them, the one with the smaller number will disappear and the remaining cards will move one step ahead so there is no empty space in between.
Alice gave Bob the numbers written on the initial set of cards. He also gave Bob the details of the final state of the game. He provided M (M ≤ N), the number of cards left in that state and the integers written on those cards.
Help Bob determine if such a state is attainable from the initial state of the game.
The first line of the input contains an integer T (1 ≤ T ≤ 100): the number of test cases.
The first line of each test case contains two space-separated integers, N (1 ≤ N ≤ 2000) and M (1 ≤ M ≤ N).
The next line contains N space-separated integers, the integers written on the initial set of cards. The following line contains M space-separated integers, the integers written on the cards in the final state of the game.
All the other integers in the input lie in the range [1, 109].
You can assume the final state to be a subsequence of the initial state.
For each test case, output two lines.
In the first line, print “Yes” (without quotes) if the final state is attainable from the initial state. Otherwise, print “No” (without quotes).
If the answer is “No”, print a “-1” in the second line. Otherwise, in the second line, print a space-separated (possibly empty) list of moves that lead to the final state.
Let i and j be the IDs in the initial set of the adjacent cards chosen for a move. k, minimum of i and j, should be mentioned in the move list to indicate that this move has been made.
If there are many possible move lists that achieve the final state, print the lexicographically earliest one.
2 6 3 1 3 2 9 4 6 1 9 6 6 3 1 3 2 9 4 6 1 3 6
Yes 2 2 4 No -1
In the first test case, the cards in position 2, 3 and 5 disappear. The moves were performed in the following way:
- Initial state: 1, 3, 2, 9, 4, 6
- Move: 2 (performed on cards with IDs 2 and 3)
- State after move: 1, 3, 9, 4, 6
- Move: 2 (performed on cards with IDs 2 and 4)
- State after move: 1, 9, 4, 6
- Move: 4 (performed on cards with IDs 4 and 5)
- State after move: 1, 9, 6
Notice that the move list: 3, 2, 4 (performed on card pairs with IDs (3, 4), (2, 4), and (4, 5) respectively) or 2, 2, 5 (performed on card pairs with IDs (2, 3), (2, 4), and (5, 6) respectively) also produce the final state but aren’t the lexicographically smallest one.
In the second case, there is no way to attain the final state from the initial one.
Labib666Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms. →