Robot Pathfinding with Teleporters

You are given a grid representing a maze where a robot starts at position S and needs to reach the destination E. Walls are represented by # while open cells are denoted by .. Additionally, some cells contain uppercase letters (other than S and E) which act as teleporters: if the robot steps on one, it can instantly move to any other cell with the same letter. Your task is to determine whether the robot can reach from S to E using any valid sequence of movements, including teleportation.

The challenge requires you to perform a breadth-first search (BFS) on the grid while also handling teleportation in an efficient manner. To avoid redundant moves, for each teleporter type, ensure that the teleportation links are used only once.

Note: The grid dimensions and the number of test cases are relatively small, so a straightforward BFS approach is sufficient.

inputFormat

The input begins with an integer T representing the number of test cases. Each test case starts with two integers N and M — the number of rows and columns of the grid respectively. This is followed by N lines, each containing a string of M characters. In the grid, S marks the starting cell, E the ending cell, # indicates walls, . indicates empty spaces, and any uppercase letter (except S and E) is a teleporter.

outputFormat

For each test case, output a single line with YES if the robot can reach the destination, or NO if it cannot.

## sample

3
5 5
.....
.S#.T
..###
T.#.E
.....
2 3
S#E
###
3 4
S..B
..#.
B..E

YES
NO
YES

</p>