B. Толкание шаров
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ecrade есть сетка размером $$$n \times m$$$, изначально пустая, и он толкнул в нее несколько (возможно, ноль) шаров.

Каждый раз он может толкнуть один шар в сетку либо с самого левого края определенной строки, либо с самого верхнего края определенного столбца сетки.

Когда шар движется к позиции:

  • Если изначально в этой позиции нет шара, входящий шар остановится и займет эту позицию.
  • Если в этой позиции уже есть шар, входящий шар остановится и займет эту позицию, в то время как оригинальный шар продолжит движение к следующей позиции в том же направлении.

Обратите внимание, что если строка или столбец заполнены (т.е. все позиции в этой строке или столбце заняты шарами), он не может толкнуть шар в эту строку или столбец.

Учитывая конечное состояние, вам нужно определить, возможно ли Ecrade толкнуть шары, чтобы достичь конечного состояния.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 50$$$).

За ней следуют $$$n$$$ строк, каждая из которых содержит ровно $$$m$$$ символов и состоит только из $$$0$$$ и $$$1$$$, описывающих конечное состояние сетки. В позиции сетки есть шар, если и только если соответствующая позиция в данном входе равна $$$1$$$.

Гарантируется, что сумма $$$n\cdot m$$$ по всем наборам входных данных не превышает $$$10\,000$$$.

Выходные данные

Для каждого набора входных данных выведите «Yes» (без кавычек), если Экраде может толкнуть шары, чтобы достичь конечного состояния, и «No» (без кавычек) в противном случае.

Вы можете выводить «Yes» и «No» в любом регистре (например, строки «YES», «yEs» и «yes» будут распознаны как правильный ответ).

Пример
Входные данные
5
3 3
001
001
110
3 3
010
111
010
3 3
111
111
111
3 3
000
000
000
3 3
000
000
001
Выходные данные
YES
YES
YES
YES
NO
Примечание

Для простоты, если Ecrade толкает шар с самого левого края $$$i$$$-й строки, мы называем операцию $$$\text{ROW}\ i$$$; если он толкает шар с самого верхнего края $$$i$$$-го столбца, мы называем операцию $$$\text{COL}\ i$$$.

Для интуитивного понимания, ненулевое число $$$x$$$ в матрице, приведенной ниже, представляет собой $$$x$$$-й шар, который был толкнут.

В первом наборе входных данных возможная последовательность операций:

$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 3}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}0&0&0\\0&0&0\\2&1&0\end{pmatrix}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3} \begin{pmatrix}0&0&4\\0&0&3\\2&1&0\end{pmatrix}$$$

Во втором наборе входных данных возможная последовательность операций:

$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 2} \begin{pmatrix}0&0&0\\3&2&1\\0&0&0\end{pmatrix}\xrightarrow{\text{COL}\ 2}\xrightarrow{\text{COL}\ 2} \begin{pmatrix}0&5&0\\3&4&1\\0&2&0\end{pmatrix}$$$

В третьем наборе входных данных возможная последовательность операций:

$$$\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}\xrightarrow{\text{ROW}\ 1}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}1&0&0\\2&0&0\\3&0&0\end{pmatrix}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3}\xrightarrow{\text{COL}\ 3} \begin{pmatrix}1&0&6\\2&0&5\\3&0&4\end{pmatrix}\xrightarrow{\text{ROW}\ 1}\xrightarrow{\text{ROW}\ 2}\xrightarrow{\text{ROW}\ 3} \begin{pmatrix}7&1&6\\8&2&5\\9&3&4\end{pmatrix}$$$