零和路径

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个 $n\times m$ 网格，每个格子的值为 $1$ 或 $-1$。你从左上角 $(1,1)$ 出发，每次可以向下或向右移动一格，最终到达右下角 $(n,m)$。

是否存在一条路径，使经过的所有格子（包括起点和终点）之和恰好为 $0$？

输入格式

第一行包含一个整数 $t$（$1\le t\le10^4$）。

每个测试用例的第一行包含两个整数 $n,m$（$1\le n,m\le1000$）。

接下来 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}\in\{-1,1\}$。

所有测试用例的 $n\cdot m$ 之和不超过 $10^6$。

输出格式

若存在所求路径，输出 YES；否则输出 NO。字母大小写不限。

样例输入 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

数据范围