Taco Hack: Reach the Treasure

In this problem, you are given a grid that represents a map. The grid is composed of characters, where '#' represents walls that block movement, '.' represents open paths, 'S' is the starting position of HackerMan, and 'T' is the location of the treasure. HackerMan can move in four directions (up, down, left, right). Your task is to determine whether HackerMan can reach the treasure from the starting position using a graph traversal algorithm such as BFS or DFS.

The movement is allowed only in the four cardinal directions. You must carefully handle the grid boundaries and ensure that you do not pass through walls.

The problem can be mathematically modeled as finding a path in a grid graph, where each cell represents a node. Two nodes are connected if they are adjacent horizontally or vertically and are not walls. In other words, given a grid (G) of dimensions (M \times N), you need to determine if there exists a path from the start cell (S) to the treasure cell (T).

inputFormat

The first line contains an integer (T) denoting the number of test cases. Each test case begins with a line containing two integers (M) and (N) ((1 \leq M, N \leq 1000)), representing the rows and columns of the grid. This is followed by (M) lines, each containing a string of length (N) composed of characters from the set {'S', 'T', '.', '#'}. It is guaranteed that each grid has exactly one 'S' and exactly one 'T'. The input is provided through standard input (stdin).

outputFormat

For each test case, output a single line containing either "YES" if HackerMan can reach the treasure, or "NO" if he cannot. The output should be printed to standard output (stdout).## sample

3
5 5
S....
.###.
..#..
.###.
....T
4 6
S..##.
.#..#.
.#..#T
.####.
3 3
S..
.#.
..T

YES
NO
YES