Path Existence in a Grid

We are given an (N \times M) grid where each cell is either passable or blocked. A cell with a value of (0) is passable and a cell with a value of (1) is an obstacle. Starting from the top-left cell (i.e. cell ((1,1))) and moving only in the four cardinal directions (up, down, left, right), the task is to determine whether there exists a path to reach the bottom-right cell (i.e. cell ((N,M))). To solve this problem, a breadth-first search (BFS) algorithm is recommended to efficiently traverse the grid and determine if such a path exists.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two space-separated integers (N) and (M), which denote the number of rows and columns of the grid respectively. This is followed by (N) lines, each containing (M) space-separated integers (either 0 or 1) representing the grid.

outputFormat

For each test case, print a single line to standard output (stdout) containing either (YES) if a valid path from the top-left to the bottom-right exists, or (NO) if no such path exists.## sample

2
3 3
0 0 1
0 1 0
0 0 0
3 3
0 1 1
1 0 1
1 1 0

YES
NO