Problem Description

Y2hlOTYw is a chess lover. However, he does not have his own chessboard.

One day, he got a piece of black-and-white grid paper with $n$ rows and $m$ columns. Of course, this is not a standard chessboard, but Y2hlOTYw does not care. He thinks that if every connected component formed by cells of the same color via 4-directional adjacency (up, down, left, right) has a rectangular shape, then this grid paper can be used as a chessboard.

Now Y2hlOTYw wants you to help determine whether this grid paper can be used as a chessboard.

Formally, let the grid paper be $G = \{(i, j) \mid 1 \le i \le n,\ 1 \le j \le m\}$, where $n$ and $m$ are positive integers. Each cell $(i,j)$ is assigned a color $\text{color}(i,j) \in \{\text{black},\text{white}\}$.

Two cells $(i,j)$ and $(i',j')$ are adjacent if and only if $|i-i'| + |j-j'| = 1$.

For a fixed color $c \in \{\text{black},\text{white}\}$, consider the subset $S_c = \{(i,j)\in G \mid \text{color}(i,j) = c\}$. Define an equivalence relation on $S_c$: two cells are equivalent if and only if there exists a sequence of cells $(i_1,j_1), (i_2,j_2), \dots, (i_k,j_k)$ such that every cell belongs to $S_c$, and for any $t$ ($1\le t\le k-1$), cell $(i_t,j_t)$ is adjacent to cell $(i_{t+1},j_{t+1})$. Each equivalence class is called a connected component. A connected component is maximal, i.e., it cannot be expanded by adding any adjacent cell of the same color.

The shape of a set of cells $R \subseteq G$ is called a rectangle if there exist integers $r_1 \le r_2$ and $c_1 \le c_2$ such that:

$$R = \{(i,j) \mid r_1 \le i \le r_2,\ c_1 \le j \le c_2\}$$

Now you need to determine whether the shape of every connected component is a rectangle.

Input Format

This problem contains multiple test cases. The first line of the input contains a positive integer $T$ ($1\le T\le 8266$), indicating the number of test cases.

Next are the descriptions of the $T$ test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n,m \le 500$), separated by a space, indicating that the grid paper has $n$ rows and $m$ columns.

The next $n$ lines: the $i$-th line contains a string $S_i$ of length exactly $m$, describing the given grid paper. It is guaranteed that $S_i$ contains only characters $\texttt{0}$ and $\texttt{1}$. For any integers $i$ and $j$ ($1\le i\le n, 1 \le j \le m$):

• If the $j$-th character of the $i$-th line is $\texttt{1}$, then the cell $(i,j)$ in row $i$ and column $j$ is black ($\text{black}$).
• If the $j$-th character of the $i$-th line is $\texttt{0}$, then the cell $(i,j)$ in row $i$ and column $j$ is white ($\text{white}$).

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2.5 \times 10^5$.

Output Format

For each test case, output one line containing a string:

• If this grid paper can be used as a chessboard, i.e., the shape of every connected component is a rectangle, output $\tt{Yes}$.
• Otherwise, output $\tt{No}$.

The answer is case-insensitive. For example, $\tt{yEs}$, $\tt{Yes}$, $\tt{yes}$, and $\tt{YES}$ will all be considered as $\tt{Yes}$.

4
2 3
110
110
4 3
110
111
111
111
5 5
00000
01110
01010
01110
00000
8 8
01010101
10101010
01010101
10101010
01010101
10101010
01010101
10101010

Yes
No
No
Yes

Hint

Translated by ChatGPT 5