Path Existence in Grid with Obstacles

You are given an ( N \times N ) grid. Your starting point is the top-left cell ((1,1)) and your goal is to reach the bottom-right cell ((N,N)). You can move in four directions: up, down, left, and right. However, some cells have obstacles, and you cannot move through them. Specifically, if an obstacle is present at cell ((x,y)), then that cell is blocked.

Your task is to determine whether there exists a path from ((1,1)) to ((N,N)) that does not go through any obstacles. Note that if either your starting cell or your target cell is blocked, a valid path does not exist.

The grid is 1-indexed, and movements outside the grid boundaries are not allowed. Use an appropriate algorithm (such as breadth-first search) to solve this problem.

inputFormat

The input is read from ( stdin ) and has the following format:

• The first line contains a single integer ( T ) denoting the number of test cases.
  
• For each test case, the first line contains two integers ( N ) (the size of the grid) and ( P ) (the number of obstacles).
  
• The next ( P ) lines each contain two integers ( x ) and ( y ) indicating the coordinates of an obstacle.

outputFormat

For each test case, print a single line to ( stdout ) containing either "YES" if there exists a path from ((1,1)) to ((N,N)), or "NO" if no such path exists.## sample

6
5 3
3 3
3 4
4 3
5 1
5 5
2 0
2 2
1 2
2 1
3 1
2 2
3 1
1 1

YES
NO
YES
NO
YES
NO