[Solution] Zero Path Codeforces Solution

[Solution] Zero Path Codeforces Solution

C. Zero Path

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a grid with n$n$ rows and m$m$ columns. We denote the square on the i$i$-th (1≤i≤n$1\le i\le n$) row and j$j$-th (1≤j≤m$1\le j\le m$) column by (i,j)$(i,j)$ and the number there by aij$a_{ij}$. All numbers are equal to 1$1$ or to −1$-1$.

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)$(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 a11$a_{11}$ and anm$a_{nm}$) is 0$0$?

Input

Each test contains multiple test cases. The first line contains the number of test cases t$t$ (1≤t≤104$1\le t\le {10}^4$). Description of the test cases follows.

Solution Click Below:-  CLICK HERE

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

Each of the following n$n$ lines contains m$m$ integers. The j$j$-th integer on the i$i$-th line is aij$a_{ij}$ (aij=1$a_{ij}=1$ or −1$-1$)  — the element in the cell (i,j)$(i,j)$.

It is guaranteed that the sum of n⋅m$n\cdot m$ over all test cases does not exceed 106${10}^6$.

Subrectangle Guess Codeforces Solution

Circle Game Codeforces Solution

Zero Path Codeforces Solution

Tree Queries (Easy Version) Codeforces Solution

Tree Queries (Hard Version) Codeforces Solution

Ambiguous Dominoes Codeforces Solution

Output

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