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

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

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

Выход из точки кипения один и находится в правом нижнем углу лабиринта, то есть имеет координаты (n, m).

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

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

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
2
3 3
S..
...
T..
2 2
ST
T.
YES
NO

0.066s 0.011s 13