Dual Robots Maze Escape

Two robots, Alice and Bob, are placed on a rectangular grid with obstacles. They must navigate the grid and reach their respective goal positions. The grid is represented by M rows and N columns. A cell containing a dot ('.') is passable, while a '#' indicates an obstacle.

For each test case, you are given the starting and goal positions of both robots. Determine if there exists a path that allows both robots to reach their goals (independently) without colliding with obstacles.

Note: The robots move independently, and we only require that a valid path exists for each robot separately. The existence of a path for each robot is determined using the following BFS-based approach:

$$\text{If } P(u,v)=\min_{\text{paths}}\text{steps from } u \text{ to } v, \text{ then the answer is } YES \text{ if } P(\text{start}_A, \text{goal}_A)\neq \infty \text{ and } P(\text{start}_B, \text{goal}_B)\neq \infty.$$

inputFormat

The input is given via stdin with the following format:

T
M N
Ax Ay Bx By
Gx1 Gy1 Gx2 Gy2
grid_row_1
grid_row_2
...
grid_row_M
... (repeats for T test cases)

Where:

• T is the number of test cases.
• M and N represent the number of rows and columns of the grid.
• Ax Ay are the starting coordinates of Alice, and Bx By are the starting coordinates of Bob.
• Gx1 Gy1 are the goal coordinates for Alice, and Gx2 Gy2 are the goal coordinates for Bob.
• The next M lines each contain an N-character string representing the grid, where '.' denotes an open cell and '#' denotes an obstacle.

outputFormat

For each test case, output a line via stdout containing either "YES" if both robots have valid paths to their respective goals, or "NO" otherwise.

## sample

2
4 4
0 0 3 3
3 0 0 3
..#.
..#.
.#..
..#.
5 5
0 0 4 4
4 0 0 4
..#..
..##.
####.
.##..
..#..

YES
NO

</p>