409734: GYM103714 D Ловушка

D. Ловушкаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Вы попали на одно поле с тиграми, которые так и хотят Вас съесть. Поле представляет собой прямоугольную таблицу $$$n \times m$$$. Некоторые клетки поля являются стенами и через них нельзя пройти.

Единственное, что Вас спасает на данный момент — все действия, Ваши и тигров, происходят пошагово. За один шаг Вы или тигр можете переместиться в соседнюю клетку вверх, вниз, влево, вправо или остаться на месте. Вы и тигры ходите по очереди. Сначала Вы совершаете один шаг, затем все тигры совершают по одному шагу.

Чтобы спастись, Вам необходимо добраться до любого края поля, не попавшись в лапы цепких тигров — именно там Вы видите телепорт в безопасное место. Тигры прекрасно Вас видят и всегда Вас преследуют. Самое главное не допустить коварного просчета, когда Вы окажетесь на одной клетке с тигром!

Формально, Вы сможете спастись, если существует маршрут к краю поля, такой что ни в один момент времени Вы и тигр не могли бы оказаться в одной ячейке. Краем поля считается любая ячейка, которая находиться на первой или последней строке поля, или на первом или последнем столбце.

Понимая безысходность ситуации, Вы пытаетесь просчитать возможный путь до любого из телепортов. Через некоторое время, известное лишь автору этой задачи, телепорты закроются, поэтому среди доступных для побега маршрутов, выбрать надо кратчайший. Есть возможность, что такого пути вообще не существует, поэтому единственным решением будет подавать сигналы $$$SOS$$$, пока Вас кто-нибудь не услышит.

Сможете ли Вы решить эту головоломку?

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^3$$$) — размеры поля.

Следующие $$$n$$$ строк содержат по $$$m$$$ символов: '.' обозначает пустую клетку, '#' обозначает стену, 'P' обозначает клетку, в которой вы находитесь, 'T' обозначает клетку с тигром. Гарантируется, что поле содержит ровно один символ 'P'.

Выходные данные

Если Вы смогли решить головоломку, выведите $$$YES$$$ и отметьте маршрут на поле символами $$$P$$$. Если существует несколько маршрутов минимальной длины, по которым можно спастись, выберите любой. Если Ваши попытки оказались тщетными, выведите $$$SOS$$$.

ПримерыВходные данные

4 5
...T.
..#.#
#.P.#
.####

Выходные данные

YES
...T.
PP#.#
#PP.#
.####

Входные данные

4 5
..T..
..#.#
#.P.#
.####

Выходные данные

SOS

Входные данные

3 2
T#
P#
##

Выходные данные

YES
T#
P#
##

Входные данные

3 3
T##
.P#
###

Выходные данные

SOS