Word Path in a Grid

You are given a grid of characters and a word. Your task is to determine if there exists a path in the grid that starts at the top‐left cell and spells out the given word by moving in any of the four adjacent directions (up, down, left, right). Each cell can be used at most once in forming the word.

Note: The path does not need to end at the bottom‐right cell; it only needs to start from the top‐left cell.

For example, consider the grid:

a b c
 d e f
 g h i

For the word "adg", there is a valid path: (0,0) 'a' -> (1,0) 'd' -> (2,0) 'g', so the answer is "YES".

However, for the word "aei", no valid path exists starting from the top‐left cell that spells the word, so the answer is "NO".

inputFormat

The input is read from standard input and has the following format:

T
n1 m1
row1
row2
... (n1 rows with m1 characters separated by spaces)
word1
n2 m2
row1
row2
... (n2 rows with m2 characters separated by spaces)
word2
...

Here, T is the number of test cases. For each test case, the first line contains two integers n and m representing the number of rows and columns. The next n lines each contain m characters (separated by spaces) representing the grid. The last line of the test case contains the word to search for in the grid.

outputFormat

For each test case output a single line with either "YES" or "NO" indicating whether or not the word can be formed from a path starting at the top-left cell. The output is printed to standard output.

## sample

4
3 3
a b c
d e f
g h i
adg
3 3
a b c
d e f
g h i
aei
3 3
a b a
d a f
g h i
adf
1 1
a
a
a

YES
NO
NO
YES

</p>