Description

      Tiyano Playstation Company (TPC) has released a popular game in Android-based cellphone. Each instance of the game has two inputs: (1) a sequence of color blocks and (2) a 2-dimensional table. See Figure 1 for an example.

Figure 1

      The target is to merge adjacent blocks in the sequence until it is left exactly one block, with such a block being a black block. The merging of two adjacent blocks will result in a new block in the same position, whose color is specified by the 2-dimensional table. For example, in Figure 1, there is a block sequence: {red, yellow, blue, red, red, …}, if we merge the first two blocks, by the merge rules in the table, we can get a green block, and the sequence will become {green, blue, red, red, …}. At each step, you can choose two adjacent color blocks to merge as long as there is a merge rule in the table.

      However, the game designer of TPC made a mistake that some instances that you will play in the game have no solution. Unfortunately, he does not know how to check for such instances, and your task is to write a program to determine if an instance is solvable.

Input

        The input begins with t (1 <= t <= 100), the number of test cases. Each test case contains three parts.

        For each test case, the first line contains two integers n (1 <= n <= 10), which is the number of colors, and m (1 <= m <= 100), which is the length of the color sequence. After that, it gives the description of the n x n 2-dimensional matrix, M, such that M_ij is the resulting color from merging color i and color j.  Each row of M is printed on a separate line. Here, we use {0, 1, 2, …, n-1} to represent the different colors in the matrix (assume 0 is black color) and M_ij = -1 indicates that color i and color j cannot be merged. After that, it contains a line with m integers, indicating the input sequence of colors.

        Take Figure 1 for example. We use {0, 1, 2, 3, 4} to represent the five colors {black, red, yellow, blue, green}, and the matrix will be:

 1 -1  4 -1 -1

 1 -1  4  0  2

-1  3 -1  3  4

 2  4  2 -1  0

-1  0  1  3  2

and the sequence of colors is: 1 2 3 1 1 2 3 0 3 1 2 1 4 4 4 0

Output

    For each test case, print the message of “Yes” or “No” without quotes to indicate if the instance is solvable or not.

Sample Input  Download

Sample Output  Download

Tags

Discuss