You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

阿瓦最近沉迷下棋，现在他又搞来了一个 $n$ 行 $m$ 列的棋盘，其中第 $i$ 行第 $j$ 列的格子中有一个数字，用 $a_{i,j}$ 表示。

因为阿瓦头脑比较简单，所以他找来的这个棋盘中的数字只有 $1$ 和 $-1$ 两种，即 $a_{i,j}=1$ 或 $a_{i,j}=-1$。阿瓦想要从左上角 $(1,1)$ 出发，每次只能向下走或者向右走，问走到右下角 $(n,m)$ 时，所经过的路径的路径和是否可以为 $0$。

形式化的描述为，$(i,j)$ 可以走到 $(i+1,j)$ 或者 $(i,j+1)$，问是否存在一种方法从 $(1,1)$ 走到 $(n,m)$ 的路径和为 $0$。

当然，走的过程中不能超出棋盘的范围。

输入格式

本题有多组测试数据。

第一行一个整数 $t$ 表示数组组数。对于每一组数据：

第一行输入两个整数 $n$ 和 $m$ 表示棋盘的大小。

接下来有 $n$ 行 $m$ 列的整数 $a_{i,j}$ 描述棋盘中的每一个数字，且数字只有 $-1$ 和 $1$ 两种选择。

输出格式

输出有 $t$ 行，如果该组数据存在一条合法的路径，则输出 "YES"，否则输出 "NO"。（不包含双引号）

输入输出样例 #1

输入 #1

5
1 1
1
1 2
1 -1
1 4
1 -1 1 -1
3 4
1 -1 -1 -1
-1 1 1 -1
1 1 1 -1
3 4
1 -1 1 1
-1 1 -1 1
1 -1 1 1

输出 #1

NO
YES
YES
YES
NO

说明/提示

样例解释

对于第三组数据，棋盘为

1 -1 -1 -1
-1 1 1 -1
1 1 1 -1

一条路径和为 $0$ 的移动路线为 $(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3)\rightarrow (2,4)\rightarrow (3,4)$。

数据范围

对于 $30\%$ 的数据，保证 $1 \leq t,n,m \le 100$。

对于 $100\%$ 的数据，保证 $1\le t \le 10^4,1\le n,m \le 10^3,\sum {n\times m} \le 10^6$。