Задача L. Лабиринт токсиков ≡

Условие

Денис посетил вечеринку спортивных программистов в Точке кипения, где участники обсуждали различные алгоритмы. В ходе обсуждения возник спор о задачах на BFS. Одни считали их интересными, другие - душными. Через какой-то время спор почти дошел до драки между участниками, после чего любители задач на BFS назвали своих противников “токсиками” и решили закрыть их в Точке кипения. В свою очередь Точка кипения представляет собой лабиринт.

Точка кипения представлена матрицей размерностью n×m. Она может содержать следующие символы:

• ‘.’ - пустая клетка;
• ‘#’ - стена;
• ‘S’ - любитель BFS;
• ‘T’ -токсик.

Любители BFS хотят заблокировать противников, а именно заменить некоторые пустые клетки на стены так, чтобы все любители BFS смогли добраться до выхода, а все токсики остались заперты в Точке кипения.

Клетки, которые изначально содержат символы 'S' или 'T', не могут быть заблокированы, но через них можно проходить.

Помогите Денису определить, можно ли заблокировать некоторые пустые клетки в Точке кипения так, чтобы ВСЕ любители BFS смогли выйти, но при этом токсики бы не смогли. Люди могут передвигаться на соседние клетки в Точке кипения по вертикали и по горизонтали. Учтите, что разрешается не блокировать клетки вовсе и блокировать выход из точки кипения. Гарантируется, что выход из лабиринта всегда представляет собой пустую клетку.

Формат входных данных

Первая строка содержит одно целое число t (1 ≤ t ≤ 1000) - количество наборов входных данных.

Для каждого набора входных данных:

• первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 100) - размерность лабиринта;
• в каждой из следующих n строк записано m символов. Символ '.' обозначает пустую клетку, '#' - стену, 'S' - любителя BFS, а 'T' - токсика.

Формат выходных данных

Для каждого набора входных данных выведите "YES" или "NO", в зависимости от того, можно ли заменить некоторые пустые клетки на стены, чтобы удовлетворить описанным ограничениям.

Примеры тестов

2
3 3
S..
...
T..
2 2
ST
T.

YES
NO