# [Solution] Zero Path solution codeforces

Zero Path solution codeforces – You are given a grid with 𝑛n rows and 𝑚m columns. We denote the square on the 𝑖i-th (1𝑖𝑛1≤i≤n) row and 𝑗j-th (1𝑗𝑚1≤j≤m) column by (𝑖,𝑗)(i,j) and the number there by 𝑎𝑖𝑗aij. All numbers are equal to 11 or to 1−1.

## [Solution] Zero Path solution codeforces

You start from the square (1,1)(1,1) and can move one square down or one square to the right at a time. In the end, you want to end up at the square (𝑛,𝑚)(n,m).

Is it possible to move in such a way so that the sum of the values written in all the visited cells (including 𝑎11a11 and 𝑎𝑛𝑚anm) is 00? ## [Solution] Zero Path solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). Description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛,𝑚10001≤n,m≤1000)  — the size of the grid.

Each of the following 𝑛n lines contains 𝑚m integers. The 𝑗j-th integer on the 𝑖i-th line is 𝑎𝑖𝑗aij (𝑎𝑖𝑗=1aij=1 or 1−1)  — the element in the cell (𝑖,𝑗)(i,j).

It is guaranteed that the sum of 𝑛𝑚n⋅m over all test cases does not exceed 106106.

Output

For each test case, print “YES” if there exists a path from the top left to the bottom right that adds up to 00, and “NO” otherwise. You can output each letter in any case.

## [Solution] Zero Path solution codeforces

Example
input

Copy
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


## [Solution] Zero Path solution codeforces

output

Copy
NO
YES
YES
YES
NO

Note

One possible path for the fourth test case is given in the picture in the statement.