d-table-splitting-2

You are given a two-dimensional table (grid) A of N rows and  M columns.
Every cell contains a lowercase letter, one of 'a' - 'z'.

Let's call two cells of A adjacent, if they share a common side.

Let's call a set S of cells a connected region if the following three conditions are satisfied:
S is connected, i.e. every pair of cells in S can be reached from each other by moving along a path of adjacent cells of S.
All the letters written in the cells of S are the same.
It's impossible to extend it, i.e. there are no more cells of A, that can be added to S so that the first two conditions still hold.

Let's say, that a connected region S is completely inside another connected region T, if there's a cycle path of adjacent cells of T, such that all the cells of S are inside the contour (shape), formed by the cycle path.

Let's call a table acceptable if there is no connected region completely inside some other connected region.
Your task is to determine whether the given table A is acceptable, and print \text{YES} or \text{NO} accordingly.

Input format
The first line contains one integer T denoting the number of test cases in the input.

The first line of each test case description contains two integers N and M denoting the number of rows and the number of columns in A respectively.

Each of the next N lines contains a string of M lowercase letters, each denoting one row of the table A.

Output format
For each test case, output the answer in a separate line.
The answer is \text{YES} if the given table is acceptable, and \text{NO} otherwise.

Constraints

1 ≤ T ≤ 18
1 ≤ N \cdot M ≤ 10^6 (it's multiplication, not a comma)
N ≤ M.

SAMPLE INPUT
4
3 4
aaaa
abba
aaaa
3 4
aaac
abba
aaaa
4 5
xaaaa
aabca
abcca
aaaaa
6 6
aaaaaa
bbbbba
baaaba
babbba
baaaaa
bbbbbb

SAMPLE OUTPUT
NO
YES
NO
YES

Explanation

In the first test case of the sample input, the given table isn't acceptable because there is a connected region of b's completely inside a connected region of a's.

In the third test case, there are the following connected regions:
a connected region with one 'x'
a connected region with one 'b'
again, a connected region with one 'b'
a connected region with three letters 'c'
a connected region with 14 letters 'a'

Here, the given table isn't acceptable because all connected regions with b's and with c's are completely inside a connected region of a's.

Stack Limit for C++ is 8MB. You are allowed to increase it in your code, e.g. using setrlimit().

Source: hackerearth | Difficulty: MEDIUM


Solutions: